文章目录
前言
最近学到了字符串模块，然后遇到了kmp，之前的哈希一直没看明白黑皮书上的代码，所以打算以后再说。然后就是看了两天的next数组求法，不明白当出现不等情况时为什么j=next[j],在掉了两天头发下，终于搞明白了。
一、KMP算法思想
1.思想
给你两个字符串，一个主串a，一个要匹配的串s
相较于一个一个匹配，一旦遇到不相等字符时主串下一位与副串开头比较，kmp在比较时发现，遇到不同时，指向主串a的指针不需回溯，而是一直走到最后，相反，对于指向副串s的指针j回溯，
模拟：
首先正常比较，发现a!=b情况
正常情况下我们可能会让i=1,j=0,再次遍历比较
但我们不难发现对于s串，他有一个前后缀a
这里我们可以直接移动s而不改变i，减少比较回溯次数
再如
遇到不匹配，但对于s有前后缀相等情况
综上，我们每次只需记录副串s前后缀的位置，就可以知道我们j应该如何回溯了，这边就是next数组
2.next数组
从上面的模拟过程可以看出，next数组主要就是求副串s的最长相同前后缀，
下面是在哔站上找到的感觉最简单的代码，
对于一个字符串s，我们找的是指向s的指针j之前的串中前后缀相等的个数，例如
对于next[5] ( j从1开始)，前缀ab==后缀ab，所以next[5]=2+1;
以下是粗略的求一个串的next数组的过程
（具体文字思路在代码中）
3.kmp函数思路
我们只需每次遇到不匹配的时候，让j回溯到next[j]位即可，其余时候相等则i++;j++;当最终的指针j大小超过副串的长度的时候，说明匹配成功，返回匹配的开始位置即可
二、代码
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
char a[1005];
char s[1005];
int getNext(char s[],int next[]) {
int len=strlen(s);
// int len=s.lengh();
next[1]=0;
int j=0;
int i=1;
while(i<len) {
if(j==0||s[i]==s[j]) next[++i]=++j;//先i自增后再指向i位，i++; next[i]=++j
// 而next[i++]是先指向i位，再对i自增 next[i]=++j; i++;
else j=next[j]; //回溯到j位之前的前缀位置 然后在进行比较
//为什么回溯到1-j前缀的位置
//因为对于1-i位前缀和后缀是一样的，而对于前缀的前缀（即1-j位的前缀）
//同样也是后缀的前缀，
//前缀的前缀=前缀的后缀
//后缀=前缀
//后缀的前缀=后缀的后缀 = 前缀的前缀=前缀的后缀
//所以前缀(即j位前的前缀next[j])=i位的后缀,
//回溯到s[i]==s[j]，此时，j前面的必定对于i前面的有相等的字符
//因为前i项找到了前缀，
//相当于一直缩小前缀的长度，找到符合的一项
}
}
void kmp(char a[],char s[]) {
int next[1005];
int alen=strlen(a);
int slen=strlen(s);
getNext(s,next);
int res=0;
int i=0,j=0;
while(i<alen&&j<slen){
if(a[i]==s[j]){
i++;
j++;
}
else {
j=next[j];
}
}
if(j>=slen){
cout<<i-slen<<endl;
}
}
int main() {
while(cin>>a>>s) {
kmp(a,s);
}
}