初学，理解可能不是那么准确~~
Next数组的含义：next[i]表示第0个元素到第i个元素组成的字符串的最大前缀后缀。Next[0]=0显然。
所以KMP的原理就是
通过找出每一阶段最大的相等的前缀后缀，那么匹配到某个字符失配时就可以从前缀的下一个字母开始匹配，而不用再回退匹配。使复杂度降从O(m^n)到O(m+n)。
最重要的就是求next数组，而且next数组在很多题都有应用，不止KMP。
而得到next数组的原理如下：
(画风就是这么洒脱，没办法~~~)
色的如图，如果比较到p，如果p点元素和q点元素相等，那么直接S1的长度加1就是next[q]了，即next[q]=next[q-1]+1。
但是如果不等，就要在S1中找到一个短一点的字符串，如棕色的那段，那样，因为黄色的那段S2和S1是相等的，那么在S1中找到的最长前缀后缀也和S2的后缀相等，这时，如果A点那里和q相等，那么next[q]就是棕那段长度+1喽~如果不相等，再向前减，对，这个过程就是代码里那里【k=next[k];】。如果到紫色的那里B和q相同，那么next[q]为紫色的长度+1.如果一直不相等，只能是0喽~
代码如下（代码原网址链接）：
void makeNext(const char P[],int next[])
{
int q,k;//q:模版字符串下标；k:最大前后缀长度
int m = strlen(P);//模版字符串长度
next[0] = 0;//模版字符串的第一个字符的最大前后缀长度为0
for (q = 1,k = 0; q < m; ++q)//for循环，从第二个字符开始，依次计算每一个字符对应的next值
{
while(k > 0 && P[q] != P[k])//递归的求出P[0]•••P[q]的最大的相同的前后缀长度k
k = next[k-1];
if (P[q] == P[k])//如果相等，那么最大相同前后缀长度加1
{
k++;
}
next[q] = k;
}
}
但很多时候next数组的意义是:next[i]表示第0个元素到第i-1个元素组成的字符串的前缀后缀，也就是如果把上面讨论的数组定义为nexta的话，那么nexta[i]=next[i+1] , 即nexta[0]=next[1]……nexta[n-1]=next[n]，并定义next[0]=-1。
代码如下：
void GetNext()
{
//这个代码的原理和上差不多，就是改的短了些
int j = 0, k = -1;
Next[0] = -1;
while (j <= tlen)
{
if (k == -1 || T[j] == T[k])
{
Next[++j] = ++k;
}
else
k = Next[k];
}
}
int KMP_Index()
{
int i = 0, j = 0;
GetNext();
while (i < slen && j < tlen)
{
if (j == -1 || S[i] == T[j])
{
i++;
j++;
}
else
j = Next[j];
}
if (j == tlen)
return i - tlen;
return -1;
}
也可以求一个字串出现的次数，代码稍作改动即可：
int KMP_Count()
{
int ans = 0;
int i = 0, j = 0;
GetNext();
while (i != slen && j != tlen)
{
if (S[i] == T[j] || j == -1)
++i, ++j; //第一次发现还可以这样写~
else
j = Next[j];
if (j == tlen)
{
++ans;
j = Next[j];
}
}
return ans;
}
举例说明理解一下
对于tytytyty
tytytyty // ↓子串 // ↓前缀后缀 next[0] = -1 next[1] = 0 // t next[2] = 0 // ty next[3] = 1 // tyt // t next[4] = 2 // tyty // ty next[5] = 3 // tytyt // tyt next[6] = 4 // tytyty // tyty next[7] = 5 // tytytyt // tytyt next[8] = 6 // tytytyty // tytyty
KMP入门题
hdu2087 AC代码：
/*******************************************************
Problem : 2087 ( 剪花布条 ) Judge Status : Accepted
RunId : 14705531 Language : G++ Author : G_lory
Code Render Status : Rendered By HDOJ G++ Code Render Version 0.01 Beta
*******************************************************/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 1005;
char s[N]; // 原字符串
char t[N]; // 匹配子串
char nt[N]; // nt[i]表示t第0~i-1个元素组成的字符串的前缀后缀
int slen, tlen; // 字符串 s, t 的长度
void get_next()
{
int j = 0, k = -1;
nt[0] = -1;
while (j <= tlen)
{
if (k == -1 || t[j] == t[k])
{
nt[++j] = ++k;
}
else
k = nt[k];
}
}
int kmp_cnt()
{
int ans = 0;
int i = 0, j = 0;
get_next();
while (i != slen && j != tlen)
{
if (s[i] == t[j] || j == -1)
++i, ++j;
else
j = nt[j];
if (j == tlen)
{
++ans;
//j = nt[j];
j = 0;
}
}
return ans;
}
int main()
{
while (scanf("%s", s) != EOF) {
slen = strlen(s);
if (slen == 1 && s[0] == '#') break;
scanf("%s", t);
tlen = strlen(t);
printf("%d
", kmp_cnt());
}
return 0;
}
hdu1711 AC代码：
/***********************************************************
Problem : 1711 ( Number Sequence ) Judge Status : Accepted
RunId : 14705762 Language : G++ Author : G_lory
Code Render Status : Rendered By HDOJ G++ Code Render Version 0.01 Beta
************************************************************/
#include <iostream>
#include <cstdio>
using namespace std;
int ss[1000005];
int tt[10005];
int nt[10005];
int slen, tlen;
void get_next()
{
int j = 0, k = -1;
nt[0] = -1;
while (j <= tlen)
{
if (k == -1 || tt[j] == tt[k])
{
nt[++j] = ++k;
}
else
k = nt[k];
}
}
int kmp_idx()
{
int i = 0, j = 0;
get_next();
while (i < slen && j < tlen)
{
if (j == -1 || ss[i] == tt[j]) ++i, ++j;
else j = nt[j];
}
if (j == tlen)
return i - tlen;
return -1;
}
int main()
{
int T;
scanf("%d", &T);
while (T--) {
scanf("%d%d", &slen, &tlen);
for (int i = 0; i < slen; ++i) scanf("%d", ss + i);
for (int i = 0; i < tlen; ++i) scanf("%d", tt + i);
int ans = kmp_idx();
printf("%d
", ans == -1 ? -1 : ans + 1);
}
return 0;
}