本文目录
- KMP算法的next数组默认要不要+1啊
- 已知一个模式串T=“aaaba“,则在KMP算法中,其next数组中的值是 (
- KMP算法中的next数组如何计算
- 模式匹配KMP算法里面next里保存的值有什么用
- 给出字符串在KMP算法中的Next数组
- kmp算法中的next到底是什么意思啊
- 关于KMP算法中的nextval【】数组是怎么得到的
- 那个，KMP算法里面 求模式串的next[]数组的方法看不懂； 有大神能详细解释一下不，看不懂哇
KMP算法的next数组默认要不要+1啊
KMP算法，主要分为2个阶段：
求next数组。
字符串匹配
next数组，就是对给定的“匹配字符串”，求出其每一个子长度字串的“最长前缀和最长后缀相等的长度”。
匹配串，p=“aabcaabbaa“, 长度n=10。因此子串为sub：
sub = “a“
sub = “aa“
sub = “aab“
sub = “aabc“
sub = “aabca“
sub = “aabcaa“
sub = “aabcaab“
sub = “aabcaabb“
sub = “aabcaabba“
sub = “aabcaabbaa“
根据“最长前缀和最长后缀相等的长度”，可以求出对应的next数组是：
next = -1; // “a“
next = 0; // “aa“
next = -1; // “aab“
next = -1; // “aabc“
next = 0; // “aabca“
next = 1; // “aabcaa“
next = -1; // “aabcaab“
next = -1; // “aabcaabb“
next = 0; // “aabcaabba“
next = 1; // “aabcaabbaa“
2. 利用上部求出的next数组，对t和p进行匹配。要点是：
（1）循环匹配
（2）如果整个匹配上，则返回匹配位置。
（3）如果当前位置没有匹配上，则：如果对应next[x]为-1，则跳过整个p的长度；否则，回溯到其前缀位置进行匹配。匹配上，则右移next[x-1]位置；否则，右移next[x]位置。
具体到“多少次字符匹配”，在编制的程序里加上统计的语句，最后输出。真要一个个字符统计，很容易出错。
已知一个模式串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）”。
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]个字符的地方，这样就少了很多重复的无效的比较和移动。
模式匹配KMP算法里面next里保存的值有什么用
next数组存储的数据是用来当模式串与主串不匹配的时候要模式串回退到第几个字符与主串再重新匹配，我们知道KMP算法的主串是不回朔的，当不匹配的时候我们不是退回到开始位置重新匹配，而是利用已经匹配的结果将模式串回朔到下一个位置，这个位置比开始位置更近一步;
简单的说就是next[ j ]的值保存的是当模式串中第 j 个字符与主串第 i 个字符不匹配时候，模式串中的哪个字符 重新与主串第 i 个再匹配，这样总的字符比较次数比从开始位置比较的次数就少了。
给出字符串在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;
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
}
}
扩展资料：
设主串（下文中我们称作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 跟 W 匹配，如果相同则匹配下一个字符，直到出现不相同的情况，此时会丢弃前面的匹配信息，然后把T 跟 W匹配，循环进行，直到主串结束，或者出现匹配成功的情况。这种丢弃前面的匹配信息的方法，极大地降低了匹配效率。
而在KMP算法中，对于每一个模式串我们会事先计算出模式串的内部匹配信息，在匹配失败时最大的移动模式串，以减少匹配次数。
参考资料来源：百度百科-kmp算法
kmp算法中的next到底是什么意思啊
先看看next数据值的求解方法
位序 1 2 3 4 5 6 7 8
模式串 a b a a b c a c
next值 0 1 1 2 2 3 1 2
next数组的求解方法是：
1.第一位的next值为0
2.第二位的next值为1
后面求解每一位的next值时，根据前一位进行比较
3.第三位的next值：第二位的模式串为b ,对应的next值为1;将第二位的模式串b与第一位的模式串a进行比较，不相等；则第三位的next值为1
4.第四位的next值：第三位的模式串为a ,对应的next值为1;将第三位的模式串a与第一位的模式串a进行比较，相同，则第四位的next值得为2
5.第五位的next值：第四位的模式串为a，对应的next值为2;将第四位的模式串a与第二位的模式串b进行比较，不相等；第二位的b对应的next值为1,则将第四位的模式串a与第一位的模式串a进行比较，相同，则第五位的next的值为2
6.第六位的next值：第五位的模式串为b，对应的next值为2;将第五位的模式串b与第二位的模式中b进行比较，相同，则第六位的next值为3
7.第七位的next值：第六位的模式串为c，对应的next值为3;将第六位的模式串c与第三位的模式串a进行比较，不相等；第三位的a对应的next值为1，则将第六位的模式串c与第一位的模式串a进行比较，不相同，则第七位的next值为1
8.第八位的next值：第七位的模式串为a，对应的next值为1;将第七位的模式串a与第一位的模式串a进行比较，相同，则第八位的next值为2
以上这种分析方法，位序是从1开始的，如果位序从0开始，刚第一位的next值为-1,后面的方法则相同
关于KMP算法中的nextval【】数组是怎么得到的
KMP 算法我们有写好的函数帮我们计算 Next 数组的值和 Nextval 数组的值，但是如果是考试，那就只能自己来手算这两个数组了，这里分享一下我的计算方法吧。
计算前缀 Next[i] 的值:
我们令 next = -1 。从 next 开始，每求一个字符的 next 值，就看它前面是否有一个最长的“字符串“和从第一个字符开始的“字符串“相等(需要注意的是，这2个“字符串“不能是同一个“字符串“)。如果一个都没有，这个字符的 next 值就是0；如果有，就看它有多长，这个字符的 next 值就是它的长度。
计算修正后的 Nextval[i] 值:
我们令 nextval = -1。从 nextval 开始，如果某位(字符)与它 next 值指向的位(字符)相同，则该位的 nextval 值就是指向位的 nextval 值(nextvalue[i] = next[ next[i] ])；如果不同，则该位的 nextval 值就是它自己的 next 值(nextvalue[i] = next[i])。
举个例子:
计算前缀 Next[i] 的值:
next = -1;定值。
next = 0;s前面没有重复子串。
next = 0;s前面没有重复子串。
next = 0;s前面没有重复子串。
next = 1;s前面有重复子串s = ’a’和s = ’a’。
next = 2;s前面有重复子串s = ’ab’和s = ’ab’。
next = 3;s前面有重复子串s = ’abc’和s = ’abc’。
next = 4;s前面有重复子串s = ’abca’和s = ’abca’。
计算修正后的 Nextval[i] 值:
nextval = -1;定值。
nextval = 0;s != s，nextval = next = 0。
nextval = 0;s != s，nextval = next = 0。
nextval = -1;s == s，nextval = next = -1。
nextval = 0;s == s，nextval = next = 0。
nextval = 0;s == s，nextval = next = 0。
nextval = -1;s == s，nextval = next = -1。
nextval = 4;s != s，nextval = next = 4。
那个，KMP算法里面 求模式串的next[]数组的方法看不懂； 有大神能详细解释一下不，看不懂哇
对于next数组
也就是子串的某个位置与自身的公共前缀的最后匹配位置。
这样讲可能有点抽象，说白了就是子串以该位置为最末位，自己和自己匹配的最长公共前缀。
而在进行next数组的第i个位置的求值时，该位置以前的所有next值已经求出，因此我们可以借助之前求出的next值来更新此刻next[i]的值。
所以时间复杂度为O(2*m)
拿ababac来说：
第一步：
ababac
_ababac
i，j在一开始就失配，即next=0。
第二步：
ababac
__ababac
i，j在第3位匹配，next=1
同理：next=2，next=3，next=4
在i=6，j=4时失配。
因此，将j=next[j]+1，i++，也就是匹配串后移。
即：
ababac
______ababac
此时，两串失配，next=0
求next数组代码：
int next;
char str2;
void get_next()
{
int len2=strlen(str2);
int i=1,j=0;
while(i《len2)
{
if(j==0 || str2[i]==str2[j])
{
i++;j++;
next[i]=j;
}
else
j=next[j];
}
}
