Algorithm/kmp算法.md
https://www.bilibili.com/video/av22409335
next数列求法
abaabcac
首先列出所有前缀,再计算相同前后缀的长度
前缀 | 长度 |
---|---|
a | 0 |
ab | 0 |
aba | 1 |
abaa | 1 |
abaab | 2 |
abaabc | 0 |
abaabca | 1 |
abaabcac | 0 |
得到00112010
,叫做maxL数列
maxL数列去掉最后一个值,前面加上-1,得到-10011201
-10011201
每个值+1,得到01122312
,这个数列是next数列
maxL00112010
next01122312
根据顺序检查maxL和next的值是否想等,若不相等,输入对应next的值,若相等,填入对应序号为next值的nextval值(这里非常绕)
得到01020302
,这个就是nextval数列
代码
(待续)
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
return haystack
def preTable(needle: str):
if __name__ == '__main__':
obj = Solution()
a="hello"
b="ll"
a="ababcabarababcabaa"
b="ababcabaa"
print(obj.strStr(a, b))