kpm算法next

⑴ 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算法的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值

暂时只帮你改正了编译错误：

#include<iostream>
using namespace std;
#include<string.h>
typedef struct
{
char data[20];
int length;
}sqstring;
void getnext(sqstring* t,int next[])
{
int j,k;
j=0;
k=-1;
next[0]=-1;
while(j<t->length-1)
{
if(k==-1||(t->data[j]=t->data[k]))
{ j++; k++;
next[j]=k;
}
else k=next[k];
}
}
main()
{
int i,JG[20];
sqstring* t;
t=(sqstring *)malloc(sizeof(sqstring));
char h[20];
gets(h);
for(i=0;h[i]!='\0';i++)
t->data[i]=h[i];
t->length=i;
getnext( t, JG);
for(i=0;i<=20;i++)
cout<<JG[i]<<endl;
}

⑷ 关于KMP算法，next第一个值到底是什么！

上代码,有详细说明
public class KMP {

String model = "abcdabce";
// String model = "abcabcabd";
// String model = "aaaab";
// String model = "";
char[] tempModel = model.toCharArray();

String str = "";
char[] tempStr = str.toCharArray();

int[] backto = new int[model.length()];
int[] next = new int[model.length()];

//查找用例
public void findStr(){
int i=0;
int j=0;
while(i<tempStr.length){
if(tempStr[i] == tempModel[j]){
i++;
j++;
}else{
j = backto[j];
if(j<0){
i++;
j++;
}
}

if(j == tempModel.length){
System.out.println(i+" "+tempStr[i-1]);
j=0;
}
}
}

/**
* a a a a b
* -1 -1 -1 -1 3
*
* a b c d a b c e
* -1 0 0 0 -1 0 0 3
*/
public void next(){
int i=0, //模式串下标,即当前位置.开始为0
k=-1;//k表示字符串在位置i之前已匹配的子串最长长度.类似于模式串的下标(从0开始)
next[i]=-1;//第一个next为-1
while(i+1<tempModel.length){//i 模式串的当前位置,因为第一个next为-1,所以从第二个开始,往前查找模式长度
if(k == -1 //初始,k,i直接自加:k=0,i=1
|| tempModel[k] == tempModel[i]){//比较第k个字符和第i个字符
i++;
k++;
if(tempModel[k] != tempModel[i]){//比较第k+1个字符和第i+1个字符不相等,说明k为当前模式最长长度.
next[i] = k;//k最小为0,因为i是从第二个开始的
}else{//第k+1个字符和第i+1个字符相等,说明第i+1个字符比较不同后,可后推到第next[k]个字符开始比较
next[i] = next[k];
}
}else{//往后找k值,此时k值表现为模式串的下标
k = next[k];
}
}
}

public void start(){
System.out.println("--------------------------------");
next();
//CommonUtil.printCharAndIntArray(tempModel,next);
}

public static void main(String[] args){
new KMP().start();
}
}

⑸ 那个，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数组存储的数据是用来当模式串与主串不匹配的时候要模式串回退到第几个字符与主串再重新匹配，我们知道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]=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

}

}

(7)kpm算法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值的问题

额这个问题之前没多久给别人解答过，我就直接搬过来了……
————————————————————————————————————————
好吧~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[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数组的问题

字符串如果是以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]说明虽然对称，但是对称后面的值和当前的字符值不相等，所以继续递推。

(10)kpm算法next扩展阅读：

kmp算法完成的任务是：给定两个字符串O和f，长度分别为n和m，判断f是否在O中出现，如果出现则返回出现的位置。常规方法是遍历a的每一个位置，然后从该位置开始和b进行匹配，但是这种方法的复杂度是O(nm)。kmp算法通过一个O(m)的预处理，使匹配的复杂度降为O(n+m)。