KMP算法
Kunth-Morris-Pratt字符串查找算法。在一个字符串中查找一个词出现的位置。
emmmm看了两天，算是明白意思了。
B站上有个UP讲的很好啊。
我也不知道我怎么才能记住KMP。
字符原串比匹配串长，所以我们想不移动原串。
把匹配串来回移动去和原串比较。
但是匹配串也不要每次出现没匹配成功，就从刚才没成功的头的下一位开始匹配。
因为之前匹配成功的一部分也许还有前缀后缀一样的呢！
所以我们把匹配串的每个位置的最长前缀后缀求出来就能减少很多移动次数呢。
那么求这个最长前缀后缀相同的字母个数的方式……
就相当于用自己的本身去和自己的本身匹配，这就和前面求匹配串去匹配原串是一样的……
利用已经匹配成功的部分得到的信息减少之后要移动的次数，也就是说利用之前求好的最长前缀后缀相同字母个数移动。
求next数组也是用了KMP， KMP本身里面就用上KMP了。
代码语言：auto复制#include "cstdio"
#include "iostream"
#include "cstring"
using namespace std;
int ne[20];///这个数组中盛放的是匹配字符串的next值
void GetNext(char *a)///这个函数是为了标记匹配字符串的next值
{
int len = strlen(a);///先求字符串的长度，便于循环赋值
int i = 0, j = -1;
ne[0] = -1;
while(i < len)
{
if(j == -1 || a[i] == a[j])
{
ne[ i] = j;
}
else j = ne[j];
}
}
///实际上每求一个next值要循环两遍
int KMP(char *a, char *b)
{
int lena = strlen(a);
int lenb = strlen(b);
int i = 0, j = 0;
while (i < lena && j < lenb)
{
if(j == -1 || a[i] == b[j])
{
j ;
i ;
}
else
j = ne[j];
}
if(j == lenb)
return i-j 1;
else
return -1;
}
int main()
{
char s[100];///this is the main
char f[100];///this is the one to be found
scanf("%s", &s);
scanf("%s", &f);
GetNext(f);
cout << KMP(s,f) << endl;
return 0;
}
