kmp算法next数组前两个

Ⅰ 给出字符串在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

}

}

(1)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算法中，对于每一个模式串我们会事先计算出模式串的内部匹配信息，在匹配失败时最大的移动模式串，以减少匹配次数。

Ⅱ 那个，KMP算法里面 求模式串的next[]数组的方法看不懂； 有大神能详细解释一下不，看不懂哇

对于next[]数组
也就是子串的某个位置与自身的公共前缀的最后匹配位置。
这样讲可能有点抽象，说白了就是子串以该位置为最末位，自己和自己匹配的最长公共前缀。

而在进行next[]数组的第i个位置的求值时，该位置以前的所有next[]值已经求出，因此我们可以借助之前求出的next[]值来更新此刻next[i]的值。

所以时间复杂度为O(2*m)

拿ababac来说：
第一步：
ababac
_ababac
i，j在一开始就失配，即next[2]=0。

第二步：
ababac
__ababac
i，j在第3位匹配，next[3]=1
同理：next[4]=2，next[5]=3，next[6]=4

在i=6，j=4时失配。

因此，将j=next[j]+1，i++，也就是匹配串后移。
即：
ababac
______ababac
此时，两串失配，next[7]=0

求next[]数组代码：
int next[100];
char str2[100];
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];
}
}

Ⅲ 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]个字符的地方，这样就少了很多重复的无效的比较和移动。