KMP

https://www.zhihu.com/question/21923021/answer/37475572

28. 找出字符串中第一个匹配项的下标

模式串：abababzababab

第一步：一边遍历模式串，一边构造next数组。

• next[i]表示字符串s[0:i+1]的前缀和后缀最大的公共长度
• 初始化j=0，i从1遍历到n-1。j的位置表示，此时s[:j]是公共前后缀
• 遍历时，如果此时有公共前后缀，不断比较s[i]和s[j]，一旦发现他们不同，则在循环中回退j，直到s[:j]成为公共前后缀。回退到此时的次长公共前后缀，将j移动到next[j-1]即可
• 再次比较s[i]和s[j]，如果相同，则移动j，并且为next[i]赋值

第二步：比较两个字符串
abeababeabf
abeabf

• i遍历字符串，j指向模式串。一次循环中，j的位置表示needle[0:j]和字符串匹配
• 当此时有匹配，检查haystack[i]与needle[j]是否相同，如果不相同，回退j至next[j-1]
• 再次比较haystack[i]与needle[j]，如果相同，移动j