kmp算法next
‘壹’ kmp算法next(j)怎么算出来的
int first=-1,last=0;
len=strlen(ch);
while(last<len){
if(ch[first]==ch[last] || first==-1){
first++;last++;
next[last]=first;
}
else
first=next[first];
}
用自己和自己KMP然后得出next[]
最后的出来的就是next[]了，当然我这个next[]是初值为-1的，你书上写的应该是最大匹配值，就是将我的全部左移一位的结果
‘贰’ 模式匹配KMP算法里面next里保存的值有什么用
next数组存储的数据是用来当模式串与主串不匹配的时候要模式串回退到第几个字符与主串再重新匹配，我们知道KMP算法的主串是不回朔的，当不匹配的时候我们不是退回到开始位置重新匹配，而是利用已经匹配的结果将模式串回朔到下一个位置，这个位置比开始位置更近一步;
简单的说就是next[ j ]的值保存的是当模式串中第 j 个字符与主串第 i 个字符不匹配时候，模式串中的哪个字符 重新与主串第 i 个再匹配，这样总的字符比较次数比从开始位置比较的次数就少了。
‘叁’ KMP算法求next数组的问题
字符串如果是以0为下标的话next[7]是0，只有最后一位与第一位相等。
在第i个字符前面的i-1个字符里面，
从开头开始的1个字符与最后1个字符是否相等，若不是，则next[i]=0；
从开头开始的2个字符与最后2个字符是否相等，若不是，则next[i]=1；
从开头开始的3个字符与最后3个字符是否相等，若不是，则next[i]=2；
前缀next数组的求解算法：
void SetPrefix(const char *Pattern, int prefix[])
{
int len=CharLen(Pattern);//模式字符串长度。
prefix[0]=0;
for(int i=1; i<len; i++)
{
int k=prefix[i-1];
//不断递归判断是否存在子对称，k=0说明不再有子对称，Pattern[i] != Pattern[k]说明虽然对称，但是对称后面的值和当前的字符值不相等，所以继续递推。
(3)kmp算法next扩展阅读：
kmp算法完成的任务是：给定两个字符串O和f，长度分别为n和m，判断f是否在O中出现，如果出现则返回出现的位置。常规方法是遍历a的每一个位置，然后从该位置开始和b进行匹配，但是这种方法的复杂度是O(nm)。kmp算法通过一个O(m)的预处理，使匹配的复杂度降为O(n+m)。
‘肆’ KMP算法中的next数组如何计算
一个串的next数组，可以这样理解
对于next[i]的值，等于该串0~i-1的这个串中，前几个字符组成的串，与后几个字符完全相同。
举个例吧，ababc，next数组下标就是0~4的范围啦~~
首先next[0]=0，这是肯定的，其实next[0]没意义。。。
计算next[1]，先看原串该位置之前的子串，即a，从前往后数1，与从后往前数1，串都是a，相等，故next[1]=1
然后next[2]，前缀串为ab，从前往后数1，与从后往前数1，子串分别为a,b，不等，所以next[2]=0
next[3]，对于前缀串aba，从前往后数1，与从后往前数1，串都是a相等。但是，数到2时，ab与ba不等，故next[3]=1
对于next[4]，前缀串abab，虽然去长度1时，子串不等。但数到2时，子串均为ab，相等。故next[4]=2
以此类推，就是数前缀串中，前数几个与后数几个，取到子串相等时，最大数到几。当然，这样数不能数到尽头。。。
‘伍’ 谁能解释数据结构中KMP算法的next函数
假如str的前j个字符是前i个字符的后缀(j<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算法求next值的问题
额这个问题之前没多久给别人解答过，我就直接搬过来了……
————————————————————————————————————————
好吧~KMP当初我也想了挺久的~很巧妙的算法啊！相必复制网络什么的你也不会看的了所以我手打吧…下面是我的理解~
为了解说方便我把长的称为文本串，短的称为目标串~
常规的匹配算法是把目标串一位一位地右移，跟文本串比较，而KMP则是跳着右移~
举几个例子相信你就懂了
————————————————————————————————————————
比如有一目标串为ababaca，当前位置匹配了前5个，也就是匹配了ababa，后面两个不匹配
这说明了文本串当前位置也是ababa
显然右移一位是不行的，因为从目标串可以看出(abab)a与a(baba)括号里的内容不相等
而右移两位是可能可行的~因为可以看出(aba)ba与ab(aba)括号里的内容是相等的，这意味着移动两位后，目标串前三位aba是肯定匹配的~因为移动前也匹配~
————————————————————————————————————————
再举一个例子~比如有目标串abcab，当前位置匹配了前两个ab
那么就需要右移3个位置，因为(ab)cab与abc(ab)括号里内容相同，移动后有可能会匹配~
————————————————————————————————————————
懂了么？表达能力有限…我也不能讲得更好了…具体代码网上一大堆，《算法导论》里面也有~我当初就是在算导里学会的！
如果懂了，希望有追加分啊，手打累死！！！
不懂的话，追问吧……
‘柒’ kmp算法中的next到底是什么意思啊
next[j]表代表j之前的字符串的真前缀和真后缀最大匹配长度，它的构成和kmp算法思想一致，只需要置next[0]=-1，再逐次推出next[j]的值
‘捌’ 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算法的next存什么
即使算法是特定的，存什么内容也是实现相关的。
对你这个数据设定，我猜测：
next[k] 表示的是，若目标字符与第 k 个字符不匹配时，则‘下一步’尝试将之和第几个字符做比较。
index:-1012345
value:|abcabd
next:-100012
‘拾’ 给出字符串在KMP算法中的Next数组
逐个查找对称串。
只要循环遍历这个子串，分别看前1个字符，前2个字符，3个... i个 最后到15个。
第1个a无对称，所以对称程度0
前两个ag无对称，所以也是0
依次类推前面0-4都一样是0
最后一个是0～3都一样是0
前缀next数组的求解算法：
void SetPrefix(const char *Pattern, int prefix[])
{
int len=CharLen(Pattern);//模式字符串长度。
prefix[0]=0;
for(int i=1; i<len; i++)
{
int k=prefix[i-1];
//不断递归判断是否存在子对称，k=0说明不再有子对称，Pattern[i] != Pattern[k]说明虽然对称，但是对称后面的值和当前的字符值不相等，所以继续递推
while( Pattern[i] != Pattern[k] && k!=0 )
k=prefix[k-1]; //继续递归
if( Pattern[i] == Pattern[k])//找到了这个子对称，或者是直接继承了前面的对称性，这两种都在前面的基础上++
prefix[i]=k+1;
else
prefix[i]=0; //如果遍历了所有子对称都无效，说明这个新字符不具有对称性，清0
}
}
(10)kmp算法next扩展阅读：
设主串（下文中我们称作T）为：a b a c a a b a c a b a c a b a a b b
模式串（下文中我们称作W）为：a b a c a b
用暴力算法匹配字符串过程中，我们会把T[0] 跟 W[0] 匹配，如果相同则匹配下一个字符，直到出现不相同的情况，此时会丢弃前面的匹配信息，然后把T[1] 跟 W[0]匹配，循环进行，直到主串结束，或者出现匹配成功的情况。这种丢弃前面的匹配信息的方法，极大地降低了匹配效率。
而在KMP算法中，对于每一个模式串我们会事先计算出模式串的内部匹配信息，在匹配失败时最大的移动模式串，以减少匹配次数。