1

我正在尝试为编程挑战实施 rabin-karp。我的实现是正确的，但是显然太慢了（组织者对每种语言都有时间限制，而我的运行时间是限制的两倍！）

我使用多项式哈希，并使用滚动哈希策略。有没有办法加快算法？

谢谢！

（凌乱）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()))
4

0 回答 0