kmp算法
① KMP算法
算法3.5——KMP算法
1. 在串S和串T中分别设比较的起始下标i和j；
2. 循环直到S中所剩字符长度小于T的长度或T中所有字符均比较完毕
2.1 如果S[i]=T[j]，则继续比较S和T的下一个字符；否则
2.2 将j向右滑动到next[j]位置，即j=next[j]；
2.3 如果j=0，则将i和j分别加1，准备下一趟比较；
3. 如果T中所有字符均比较完毕，则返回匹配的起始下标；否则返回0；
void GetNext(char T[ ], int next[ ])
{
next[1]=0;
j=1; k=0;
while (j<T[0])
if ((k= =0)| |(T[j]= =T[k])) {
j++;
k++;
next[j]=k;
}
else k=next[k];
}
② 求kmp算法的详细解释。（最好附上能运行的程序）
t;i),那么next[i]就是所有这样的j的最大值
形象地说,就是假如第i+1个字符匹配失败之后,下一个可能匹配位置至少应该往后挪动多少
就"abaabc"而言
next[1]=0
next[2]=0
next[3]=1
next[4]=1
next[5]=2
next[6]=0
计算过程基本上抄自算法导论,假设str长度为n
k=0;//k表示当前匹配了多少位
next[1]=0;
for (i=1;i<n;i++)
{
while (k && str[i]!=str[k]) k=next[k];
if (str[i]==str[k]) k++;
next[i+1]=k;
}
之后计算str和某个长度为m的字符串text匹配的过程基本上是一样的
k=0;//用于记录str最长能够有前k位是text的前i+1个字符的后缀
for (i=0;i<m;i++)
{
while (k && text[i]!=str[k]) k=next[k];//发现不能匹配的时候就把str往后挪
if (text[i]==str[k]) k++;
if (k==n) printf("在位置%d处找到一个匹配\n",i+1-n);
}
对照着后面这一段很容易理解第一段
③ KMP算法问题
一般的KMP算法
讨论一般情况。
假设
主串：s: ‘s⑴ s⑵ s⑶ ……s(n）’ ;
模式串 ：p: ‘p⑴ p⑵ p⑶…..p(m）’
把课本上的这一段看完后，继续
现在我们假设 主串第i个字符与模式串的第j(j<=m）个字符‘失配’后，主串第i个字符与模式串的第k(k<j）个字符继续比较
此时，s(i）≠p(j），有
主串：s⑴…… s(i-j+1）…… s(i-1） s(i) ………….
|| （相配） || ≠（失配）
匹配串：p⑴ ...........p(j-1） p(j)
由此，我们得到关系式：
‘p⑴ p⑵ p⑶…..p(j-1）’ = ’ s(i-j+1）……s(i-1）’
由于s(i）≠p(j），接下来s(i）将与p(k）继续比较，则模式串中的前（k-1）个字符的子串必须满足下列关系式，并且不可能存在 k’>k 满足下列关系式：（k<j),
‘p⑴ p⑵ p⑶…..p(k-1）’ = ’ s(i-k+1）s(i-k+2）……s(i-1）’
即：
主串：s⑴……s(i-k +1） s(i-k +2） ……s(i-1） s(i) ………….
|| （相配） || ||（有待比较）
匹配串：p⑴ p⑵ ……..... p(k-1） p(k)
我们把前面总结的关系综合一下
有：
s⑴…s(i-j +1）… s(i-k +1） s(i-k +2） …… s(i-1） s(i) ……
|| （相配） || || || ≠（失配）
p⑴ ……p(j-k+1） p(j-k+2） …...... p(j-1） p(j)
|| （相配） || ||（有待比较）
p⑴ p⑵ ……...... p(k-1） p(k)
由上，我们得到关系：
'p⑴ p⑵ p⑶…..p(k-1）’ = ' p(j-k+1）p(j-k+2）……p(j-1）’
接下来看“反之，若模式串中存在满足式（4-4）。”这一段。看完这一段，如果下面的看不懂就不要看了。直接去看那个next函数的源程序。（伪代码）
K 是和next有关系的，不过在最初看的时候，你不要太追究k到底是多少，至于next值是怎么求出来的，我教你怎么学会。
课本83页不是有个例子吗？就是 图4.6
你照着源程序，看着那个例子慢慢的推出它来。看看你做的是不是和课本上正确的next值一样。
在理解上面代码的基础上，建议自己寻找一些KMP算法的练习，也可以自己写两个较为简单的字符串进行人脑模拟这种方法的练习，以加深对算法的理解。
④ KMP算法详细代码
private int KMP(String inText, String inMode)
{
if (inText.Length < inMode.Length)
{
return -1;
}
int[] arrNext = new int[inMode.Length + 1];
this.Next(inMode, arrNext);
int i, j; // i是主串游标 j是模式串游标
for (i = j = 0; i < inText.Length && j < inMode.Length; )
{
if (j == -1 || // 模式串游标已经回退到第一个位置
inText[i] == inMode[j]) // 当前字符匹配成功
{ // 满足以上两种情况时两个游标都要向前进一步
++i;
++j;
}
else // 匹配不成功,模式串游标回退到当前字符的arrNext值
{
j = arrNext[j];
}
}
if (j >= inMode.Length)
{
return i - inMode.Length;
}
else
{
return -1;
}
}
private void Next(String inMode, int[] arrNext)
{
arrNext[0] = -1;
for (int i = 0, j = -1; i < inMode.Length; )
{ // i是主串游标 j是模式串的游标
if (j == -1 || // 如果模式串游标已经回退到第一个字符
inMode[i] == inMode[j]) // 如果匹配成功
{ // 两个游标都向前走一步
++i;
++j;
arrNext[i] = j; // 存放当前的arrNext值为此时模式串的游标值
}
else // 匹配不成功j就回退到上一个arrNext值
{
j = arrNext[j];
}
}
}
⑤ KMP算法中的nextval函数值的原理，求详细推导
1 get_nextval(int *nextval,const char *string)
2 {
3 int num=strlen(string);
4 int i=0,j=-1;
5 nextval[0]=-1;
6 while(i<num)
7 {
8 if(j==-1||string[i]=string[j])
9 {
10 i++;
11 j++;
12 if(string[i]==string[j])
13 {
14 nextval[i]=nextval[j];
15 }
16 else
17 {
18 nextval[i]=j;
19 }
20 }
21 else
22 {
23 j=next[j];
24 }
25 }
kmp的思想主要是通过nextval数组来指示“假如在子串与主串匹配过程中在某一位(假设为 j )匹配失败（不相等）时，子串应回到的位置。”以此区别于朴素模式匹配的一旦在某位匹配失败，就从头比较的特点。所以在生成与子串等长的nextval数组时，nextval数组每一个元素标识的就应该是当在子串的第j位与主串匹配失败时，应回到子串的哪一位。
设子串string为"abqabc"。主串为"abqabqabc"；生成nextval的思想是：假设目前 j 和 i 各处string的某一个位置，对比string[j]和string[i]（代码第8行），若相等，j 和 i 都向前一步，j , i 向前一步（代码10~11行）是为了下一次匹配，同时是为了在nextval[i]记录当子串与主串匹配失败时应回到子串的哪一位继续比较下去（代码第14或18行）。比如说当子串与主串在第六位（子串的c跟主串的q）匹配失败时，我们会希望nextval[5]记录的是2，这样"ab"就不需重新匹配。
可以看到在子串的 c 之前，"abqab" 是前缀(ab)与后缀(ab)相等的，有两位，所以在nextval[5]记录 2 ，意思就是当 c 与主串匹配失败时，直接回到子串string[2]继续比较即可。
在制作nextval数组的过程中，i只会往前，j如果遇到前缀string[j]不等于后缀string[i]时会回溯，往回找，看能不能找到与后缀相等的前缀。比如子串为"abqabac"，制作nextval数组时比较到第三位(q)跟第六位(a)时，此时q不等于a，所以j往回找，拿第二位（b）跟第六位（a）比较，还是不相等，继续往回找，找到一个位（a）跟第六位（a），相等，则在nextval[5]记录nextval[0]的值，即-1，这时如果子串跟主串的匹配在子串的第六位（a）匹配失败了，则直接略过主串的这一位，子串从头开始与主串的下一位继续进行匹配。
⑥ 各位面过BAT的同学,你们有没有被考过KMP算法
三家都面过，也许是我运气好，没有碰到过。其实KMP算法效率不是很高，理解起来也不容易。如果面试官跟你聊字符串匹配算法，你完全可以说点其他算法装逼。给你一个网页，希望能帮助到你。4795369请采纳最佳答案~
⑦ 谁知道KMP算法的简易理解
int f[50];//失败函数
int i = 0, j = 1;
f[0] = -1;
for (j=1;j<n;j++)
{
i = f[j-1];
while (*(y+j) != *(y+i+1) && i>=0)
i = f[i];
if (*(y+j)==*(y+i+1))
f[j] = i+1;
else
f[j] = -1;
}
在本程序中失败函数意思为 f[j] = 最大的 k 使得匹配模板前j+1个字符中 前k+1个字符和后k+1个字符相等
所以在j的位置上匹配失败后可以跳到 f[j-1] + 1 的位置上进行匹配
不懂加QQ331012005
我们看到在简单匹配算法中，当主串和子串的字符比较不相等时，
主串的字符指针ps需返回本趟开始处的下一个字符，而子串的指针pp则回到子串的起始字符，
这种回溯显然是费时的。如果仔细观察，可以发现这样的回溯常常不是必须的。
设主串s="s0 s1 … sn－1"，模式串p="p0 p1 … pm－1"，并设字符比较在si≠pj处失配。如果考察p串，发现
p0 p1… pk－1 = pj－k pj－k+1… pj－1
p0 p1 … pj－1的前缀子串，pj－k pj－k+1… pj－1 是p0p1 … pj－1的后缀子串。由于匹配在si≠pj处失败，所以必有
pj－k… pj－2 pj－1= si－k… si－2 si－1
因此
p0… pk－2 pk－1 = si－k… si－2 si－1
那么，下一趟比较可以从si和pk处开始。
所以可以定义失败函数如下
－1(当j=0时)
f(j)= max{k|0＜k＜j且p0 p1 … pk－1= pj－k pj－k+1… pj－1}存在
0(其他情况)
设比较在si、pj处失败，f(j)≥0表示下一趟比较从si与pf(j)处开始；
f(j)=－1表示p0 si, 下一趟比较应从p0与si＋1开始。
⑧ kmp算法什么意思
KMP算法之所以叫做KMP算法是因为这个算法是由三个人共同提出来的，就取三个人名字的首字母作为该算法的名字。其实KMP算法与BF算法的区别就在于KMP算法巧妙的消除了指针i的回溯问题，只需确定下次匹配j的位置即可，使得问题的复杂度由O(mn)下降到O(m+n)。
在KMP算法中，为了确定在匹配不成功时，下次匹配时j的位置，引入了next[]数组，next[j]的值表示P[0...j-1]中最长后缀的长度等于相同字符序列的前缀。
对于next[]数组的定义如下：
1) next[j] = -1 j = 0
2) next[j] = max(k): 0<k<j P[0...k-1]=P[j-k,j-1]
3) next[j] = 0 其他
如：
P a b a b a
j 0 1 2 3 4
next -1 0 0 1 2
即next[j]=k>0时，表示P[0...k-1]=P[j-k,j-1]
因此KMP算法的思想就是：在匹配过程称，若发生不匹配的情况，如果next[j]>=0，则目标串的指针i不变，将模式串的指针j移动到next[j]的位置继续进行匹配；若next[j]=-1，则将i右移1位，并将j置0，继续进行比较。
⑨ kmp算法的介绍
KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数，函数本身包含了模式串的局部匹配信息。
⑩ kmp算法中的next到底是什么意思啊
next[j]表代表j之前的字符串的真前缀和真后缀最大匹配长度，它的构成和kmp算法思想一致，只需要置next[0]=-1，再逐次推出next[j]的值