Login light

Algorithm/kmp算法.md

https://www.bilibili.com/video/av22409335

next数列求法

abaabcac
首先列出所有前缀,再计算相同前后缀的长度

前缀长度
a0
ab0
aba1
abaa1
abaab2
abaabc0
abaabca1
abaabcac0

得到00112010,叫做maxL数列
maxL数列去掉最后一个值,前面加上-1,得到-10011201
-10011201每个值+1,得到01122312,这个数列是next数列

maxL
00112010
next
01122312
根据顺序检查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))