from time import clock
import sys
def pre(p):
    global ncomp
    n=len(p)
    prefix=[0]*n
    j=0
    for i in xrange(1,n):
        while j>0 and p[i]!=p[j]:
            ncomp+=1
            j=prefix[j-1]
        if p[i]==p[j]:
            ncomp+=1
            j=j+1
        prefix[i]=j
    return prefix
def main():
    global ncomp
    ncomp=0
    q=0
    try:
        start=clock()
        f=open("in15_4.txt","r")
        f1=open("out_34_15_4.txt","w")
        a=f.readline()
        b=f.readline()       
        f.close()
        n=len(a)
        m=len(b)
        prefix=pre(b)
        j=0
        for i in range(n):
            while j>0 and a[i]!=b[j]:
                ncomp+=1
                j=prefix[j-1]
            if a[i]==b[j]:
                ncomp+=1
                j=j+1
            if j==m:
                q=1
                z=i-m+1
                f1.write("Pattern found at index : %d" %z)
                break
        if q!=1:
                f1.write("Not Matched")        
        end=clock()
        f1.write("\nTotal comparisons are : %d" %ncomp)
        f1.write("\nTime taken by the program is : %f seconds" %(end-start))
        mem=sys.getsizeof(f)+sys.getsizeof(f1)+sys.getsizeof(q)+sys.getsizeof(a)+sys.getsizeof(b)+sys.getsizeof(n)+sys.getsizeof(m)+sys.getsizeof(prefix)+sys.getsizeof(j)+sys.getsizeof(z)
        f1.write("\nMemory used by the program is : %d bytes." %mem)
        f1.close()
    
    except IOError:
        print "File not found in the directory."
main()