讨论/技术交流/求审查一下代码/

之前看算法4断在了subString search kmp,今天打算重新开始把它看完,上午感觉完全弄明白了BMP,它为什么正确。 这是下午写的代码。不知道对不对,主要怕自以为自己弄明白了,其实并没有.没在leetcode上找到subStringSearch这么简单的题目😒

def kmp(pattern, text):
    m, n = len(pattern), len(text)
    dfa = [[0] * 26 for _ in range(m)]
    dfa[0][0] = 1
    x = 0
    for j in range(1, m):
        for i in range(26):
            dfa[j][i] = dfa[x][i]
        cur = ord(pattern[j]) - ord('a')
        dfa[j][cur] = j+1
        x = dfa[x][cur]

    j = 0
    for i in range(n):
        cur = ord(text[i]) - ord('a')
        j = dfa[j][cur]
        #print(i, j)
        if j == m: return i
    return 'no match'

m = len(pattern)
pattern = 'abcabd'
text = 'abbabcabcjfkldsjajlkcljfdlczjljfabcabdlczjljfabcabbabcacabcabcb'
i = kmp(pattern, text)
print(i, text[i+1-m: i+1])
共 4 个回复

KMP 哎呀 一不小心名字都弄错了

1

有一个bug,哈哈

1

28. 实现 strStr() 就是,你可以使用这个问题的测试用例验证你的代码是否正确。

bmp 就叫 bm(Boyer-Moore)。不知道是不是我弄错了。

1

哈哈,那就好好调试一下!