kmp算法next数组
1. kmp算法中的next到底是什么意思啊
next[j]表代表j之前的字符串的真前缀和真后缀最大匹配长度，它的构成和kmp算法思想一致，只需要置next[0]=-1，再逐次推出next[j]的值
2. 给出字符串在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
}
}
(2)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算法中，对于每一个模式串我们会事先计算出模式串的内部匹配信息，在匹配失败时最大的移动模式串，以减少匹配次数。
3. KMP算法的next数组默认要不要+1啊
KMP算法，主要分为2个阶段：
求next数组。
字符串匹配
next数组，就是对给定的“匹配字符串”，求出其每一个子长度字串的“最长前缀和最长后缀相等的长度”。
匹配串，p="aabcaabbaa", 长度n=10。因此子串为sub[10]：
sub[0] = "a"
sub[1] = "aa"
sub[2] = "aab"
sub[3] = "aabc"
sub[4] = "aabca"
sub[5] = "aabcaa"
sub[6] = "aabcaab"
sub[7] = "aabcaabb"
sub[8] = "aabcaabba"
sub[9] = "aabcaabbaa"
根据“最长前缀和最长后缀相等的长度”，可以求出对应的next数组是：
next[0] = -1; // "a"
next[1] = 0; // "aa"
next[2] = -1; // "aab"
next[3] = -1; // "aabc"
next[4] = 0; // "aabca"
next[5] = 1; // "aabcaa"
next[6] = -1; // "aabcaab"
next[7] = -1; // "aabcaabb"
next[8] = 0; // "aabcaabba"
next[9] = 1; // "aabcaabbaa"
2. 利用上部求出的next数组，对t和p进行匹配。要点是：
（1）循环匹配
（2）如果整个匹配上，则返回匹配位置。
（3）如果当前位置没有匹配上，则：如果对应next[x]为-1，则跳过整个p的长度；否则，回溯到其前缀位置进行匹配。匹配上，则右移next[x-1]位置；否则，右移next[x]位置。
具体到“多少次字符匹配”，在编制的程序里加上统计的语句，最后输出。真要一个个字符统计，很容易出错。
4. KMP 算法中 next 数组手工求解
KMP算法是一种改进的字符串匹配算法，如果不研究编码的话，手工实现还是比较简单，小型字符串甚至不需要你去求 next 数组就能看出来怎么移动。但是会有一些题目让你求解 next 数组，这里就以一个题目讲一下手工求解的过程。
例：求串 ‘ababaaababaa’ 的 next 数组
观察第一个元素，它没有前缀和后缀（串本身不能作为前缀或后缀），所以记录数据为0（这个数字表示当存在前缀和后缀相同的情况下，所能包含的最大的元素）
观察前两个元素，前缀为a，后缀为b，不相同，即没有相同的前缀和后缀，所以同样记录数据为0
观察前三个元素，存在前后缀相同的情况，为a，记录数据为1
观察前四个元素，同样存在前缀后缀相同的情况，为ab，记录数据为2
观察第五个元素，相同的前后缀为aba（ aba ba、ab aba ），记录数据为3
同理观察余下的（用加粗表示前缀、下划线表示后缀）
a baba_a_ 1
a babaa_a_ 1
ab abaa_ab_ 2
aba baa_aba_ 3
abab aa_abab_ 4
ababa a_ababa_ 5
ababaa ababaa 6
最后我们得到一组数值：0 0 1 2 3 1 1 2 3 4 5 6
在这组数开头添加 -1，并删去最后一个数值，数组变为： -1 0 0 1 2 3 1 1 2 3 1 1 2 3 4 5
所有值+1，变为：0 1 1 2 3 4 2 2 3 4 2 2 3 4 5 6，这就是我们需要的 next 数组
需要注意的是，不同的题目next[0]可能为-1，所以 -1 0 0 1 2 3 1 1 2 3 1 1 2 3 4 5 同样有可能作为 next 数组，但是这两种一定不会同时出现。
题目图片：
5. 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
以此类推，就是数前缀串中，前数几个与后数几个，取到子串相等时，最大数到几。当然，这样数不能数到尽头。。。
6. 数据结构与算法——字符串匹配问题(KMP算法)
KMP算法也是比较着名的模式匹配算法。是由 D.E.Knuth,J.H.Morrs 和 VR.Pratt 发表的一个模式匹配算法。可以大大避免重复遍历的情况。
如果使用暴风算法的话，前面五个字母完全相等，直到第六个字母 "f" 和 "x" 不相等。如下图：
T = “abcdex”
j 123456
模式串 abcdex
next[j] 011111
T = "abcabx"
j 123456
模式串T abcabx
next[j] 011123
T = "ababaaaba"
j———————123456789
模式串T——— ababaaaba
next[j]————011234223
T = "aaaaaaaab"
j———————123456789
模式串T——— aaaaaaaab
next[j]————012345678
next数组其实就是求解字符串要回溯的位置
假设，主串S= “abcababca”;模式串T=“abcdex”，由以上分析得出next数组为011111，next数组意味着当主串与模式串不匹配时，都需要从第一个的位置重新比较。
KMP算法也是有缺陷的，比如主串S=“aaaabcde”,模式串T= “aaaaax”。next的数组就是012345；
当开始匹配时，当i= 5，j = 5时，我们发现字符"b"与字符“a”不相等，如上图，j = next[5] = 4;
由于T串的第二、三、四、五位置的字符都与首位“a”相等，那么可以用首位next[1]的值去取代与它相等的后续字符的next[j],那么next数组为{0,0,0,0,0,5};
在求解nextVal数组的5种情况
7. KMP算法中的next数组值的疑问
问题1数组下标是从1开始计算 问题2数组下标从0开始
8. KMP算法中的next数组如何计算
next[i]表示的是：
在第i个字符前面的i-1个字符里面，
从开头开始的1个字符与最后1个字符是否相等，若不是，则next[i]=0,否则继续看下面；
从开头开始的2个字符与最后2个字符是否相等，若不是，则next[i]=1,否则继续看下面；
从开头开始的3个字符与最后3个字符是否相等，若不是，则next[i]=2,否则继续看下面；
……
就是这样的判断取值。
它的意思就是如果到了某个字符不匹配的情况时候，你就可以直接把模式串拖到从开头开始的那next[i]个字符等于当前字符的前next[i]个字符的地方，这样就少了很多重复的无效的比较和移动。
9. 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，继续进行比较。
10. 已知一个模式串T="aaaba",则在KMP算法中,其next数组中的值是 (
abaabcac
01122312
前两个字母next序列分别为01,直接写上
第三个"a" 时，它前一个字母为b,从头开始字母为a, a!=b所以为1
第四个"a" 时，前字母为a,从头开始字母为a,a=a,所以值为1＋1=2（相等时为串长加1）
第五个"b"，前个字母为a,从头开始a,a=a,为2
第六个"c",前个字母为b,再往前是a,ab,从头开始ab串，ab=ab，因此值为2＋1＝3
第七个字母为"a",前个字母为c,与从头开始的第一个字母不相等，所以为1
第八个为"c",前个字母为a,与开始第一个字母相等，因此为2
则返回逻辑“真（TRUE）”，反之返回逻辑“假（FALSE）”。