hashing.py

p=3
m=1000

def stringHash(txt):
    # print len(txt)
    txtHashList = [0L] * (len(txt) - 100)
    for i in xrange(0, 100):
        # print i
        txtHashList[0] += ord(txt[i])*(p**i)

    # print firstHash
    for i in range(1, len(txt)-100):
        # print i
        txtHashList[i] = ((txtHashList[i-1]-ord(txt[i-1]))/p) + (ord(txt[i+99])*(p**99))

    return txtHashList

def patternHash(s):
    hashsum=0L
    for i in range(0,100):
        hashsum=hashsum+ord(s[i])*(p**i)
    return hashsum

def main():
    with open('file2.txt') as fp:
        patlist = fp.read().splitlines()

    print patlist

    patHashList=[]

    # print len(patlist)
    for i in xrange(0, len(patlist)):
        patHashList.append(patternHash(patlist[i]))

    # print patHashList

    txtHashList=[]
    # Read text.
    with open('file1.txt') as fp1:
        txtlist = fp1.read().splitlines()

    # print txtlist

    processedInput=""
    for i in range(0, len(txtlist)):
        processedInput = processedInput + txtlist[i] + " "

    print processedInput

    txtHashList = stringHash(processedInput)

    print txtHashList


    hashDict = {}
    for j in xrange(0, len(txtHashList)):
        # print txtHashList[j]%m
        temp = processedInput[j:j+100]
        if hashDict.get(txtHashList[j]%m,0)==0 :
            hashDict[txtHashList[j]%m]= temp
        else :
            hashDict[txtHashList[j]%m][1].append(temp)

    # print hashDict

    for i in xrange(0, len(patHashList)):
        # print patHashList[i]
        if hashDict.get(patHashList[i]%m,0)!=0:
            for j in range(0, len(hashDict[txtHashList[j]%m][1]))
                if hashDict[txtHashList[j]%m][1] == patlist[i]:
                    print "FOUND!"


main()