import sys
import time
f1=open('in15_4.txt','r')
f2=open('out_24_15_4.txt','w')
st=f1.readline()
mch=f1.readline()
l1=st.split('\n')
l2=mch.split('\n')
st=l1[0]
mch=l2[0]
len1= len(st)
len2= len(mch)
out = [0] * len2
i = 0
cmp=0
x=time.clock() 
for j in range(1, len2):
    while i > 0 and mch[i] != mch[j]:
        i = out[i - 1]
    if mch[i] == mch[j]:
        i = i + 1
    out[j] = i
z = 0

for j in range(len1):
    while mch[z] != st[j] and z > 0 :
        cmp=cmp+1
        z = out[z - 1]
    if mch[z] == st[j]:
        cmp=cmp+1
        z = z + 1
    if z == len2:
        f2.write('Index=')
        f2.write(str(j - len2 + 1))
        break

w=time.clock()
f2.write('\nNo.of Comparisons='+str(cmp))
f2.write('\nTime Used='+str(w-x))
mem=sys.getsizeof(i)+sys.getsizeof(j)+sys.getsizeof(z)+sys.getsizeof(mch)+sys.getsizeof(st)
f2.write('\nMemory Used='+str(mem)) 
f1.close()
f2.close()