python - python3 rabin-karp 実装の高速化

Question

プログラミングの課題のためにラビンカープを実装しようとしています。私の実装は正しいですが、どうやら遅すぎるようです (主催者は言語ごとに時間制限を設けており、私の実行時間は制限の 2 倍です!)

多項式ハッシュを使用し、ローリング ハッシュ戦略を使用します。アルゴリズムを高速化する方法はありますか?

ありがとう！

(乱雑な)python3 コードは次のとおりです。

P = 8597
X = 3613


def read_input():
    return (input().rstrip(), input().rstrip())

def print_occurrences(output):
    print(' '.join(map(str, output)))

#return a list of indices
def get_occurrences(pattern, text):
    res = []
    lenP = len(pattern)
    lenT = len(text)
    hp = getHash(pattern)
    ht = getHash(text[0 : lenP])

    # most significant coefficient
    msc = 1
    for i in range(lenP-1):
        msc = (msc * X) % P


    for i in range(1, lenT-lenP+2):
        if (hp == ht) and (pattern == text[i-1 : i-1 + lenP]):
            res.append(i-1)
        if i-1 + lenP < lenT:
            ht = (X*(ht - ord(text[i-1]) * msc) + ord(text[i-1 + lenP])) % P
            if ht < 0:
                ht += P

    return res

def getHash(s):
    res = 0
    l = len(s)
    for i in range(l):
        res += (ord(s[i]) * (X**(l-i-1))) % P
    return res % P



if __name__ == '__main__':
    print_occurrences(get_occurrences(*read_input()))