❶ KMP算法中的nextval函数值的原理，求详细推导
1 get_nextval(int *nextval,const char *string)
2 {
3 int num=strlen(string);
4 int i=0,j=-1;
5 nextval[0]=-1;
6 while(i<num)
7 {
8 if(j==-1||string[i]=string[j])
9 {
10 i++;
11 j++;
12 if(string[i]==string[j])
13 {
14 nextval[i]=nextval[j];
15 }
16 else
17 {
18 nextval[i]=j;
19 }
20 }
21 else
22 {
23 j=next[j];
24 }
25 }
kmp的思想主要是通过nextval数组来指示“假如在子串与主串匹配过程中在某一位(假设为 j )匹配失败（不相等）时，子串应回到的位置。”以此区别于朴素模式匹配的一旦在某位匹配失败，就从头比较的特点。所以在生成与子串等长的nextval数组时，nextval数组每一个元素标识的就应该是当在子串的第j位与主串匹配失败时，应回到子串的哪一位。
设子串string为"abqabc"。主串为"abqabqabc"；生成nextval的思想是：假设目前 j 和 i 各处string的某一个位置，对比string[j]和string[i]（代码第8行），若相等，j 和 i 都向前一步，j , i 向前一步（代码10~11行）是为了下一次匹配，同时是为了在nextval[i]记录当子串与主串匹配失败时应回到子串的哪一位继续比较下去（代码第14或18行）。比如说当子串与主串在第六位（子串的c跟主串的q）匹配失败时，我们会希望nextval[5]记录的是2，这样"ab"就不需重新匹配。
可以看到在子串的 c 之前，"abqab" 是前缀(ab)与后缀(ab)相等的，有两位，所以在nextval[5]记录 2 ，意思就是当 c 与主串匹配失败时，直接回到子串string[2]继续比较即可。
在制作nextval数组的过程中，i只会往前，j如果遇到前缀string[j]不等于后缀string[i]时会回溯，往回找，看能不能找到与后缀相等的前缀。比如子串为"abqabac"，制作nextval数组时比较到第三位(q)跟第六位(a)时，此时q不等于a，所以j往回找，拿第二位（b）跟第六位（a）比较，还是不相等，继续往回找，找到一个位（a）跟第六位（a），相等，则在nextval[5]记录nextval[0]的值，即-1，这时如果子串跟主串的匹配在子串的第六位（a）匹配失败了，则直接略过主串的这一位，子串从头开始与主串的下一位继续进行匹配。
❷ C语言中nextval什么意思
C程序连接数据库了？
SQL可以用nextval函数访问SEQUENCE的值
❸ 数据结构kmp 优化算法中的nextmal 值的求法
aeth
❹ 串模式匹配的kmp算法中next[0]的值到底是0还是-1；next[1]的值又到底是1还是0
因为找next值的时候是从第一个字符开始的，规定第一个字符的next值为0，即如果第一个字符的下标为0则next[0]=0,如果第一个字符的下标是1则next[1]=0。。。因为next值将作为主串的标，数组下标不能为负数，所以next[0]不能为-1。。。
❺ 数据结构nextval值怎么求
KMP算法优化，将next[j]修正为next [next[j]]，直至两者不相等为止，更新后的数组命名为nextval。
一般手算时，从前往后，找相同字符更新即可。
❻ KMP算法中模式串的next[j]（优化版，无返回值）（也就是修正值的那个） 求大佬按下面的结构体给写出算法
用nextval[]改进next[]
还有，代码真美，看了好久
#include<stdio.h>
#define MAXSIZE 100
#include<iostream>
using namespace std;
typedef struct
{
char data[MAXSIZE];
int length;
}SqString;
void StrAssign(SqString &s,char cstr[])
{
int i;
for(i=0;cstr[i]!='\0';i++)
s.data[i]=cstr[i];
s.length=i;
}
void GetNextval(SqString t,int nextval[])
{
int j=0,k=-1;
nextval[0]=-1;
while(j<t.length)
{
if(k==-1||t.data[j]==t.data[k])
{
j++;
k++;
if(t.data[j]!=t.data[k])
{
nextval[j]=k;
}else
nextval[j]=nextval[k];
}
else
k=nextval[k];
}
}
int KMPIndex1(SqString s,SqString t)
{
int nextval[MAXSIZE],i=0,j=0;
GetNextval(t,nextval);
while(i<s.length&&j<t.length)
{
if(j==-1||s.data[i]==t.data[j])
{
i++;
j++;
}
else
j=nextval[j];
}
if(j>=t.length)
return (i-t.length);
else return -1;
}
int main()
{
SqString t,p;
StrAssign(t,"aaadaaadaaaad");
StrAssign(p,"aaaad");
cout<<KMPIndex1(t,p)<<endl;
}
❼ 求next数组和nextval数组。
next : 前缀和后缀的最长匹配数 + 1；
nextval: 第 i 个字符 （i 的下标从 1开始）若与 第next[i] 上的字符不同，nextval[i]保持为 next[i] ,否则 更新为 第next[i]上的nextval值（也就是 nextval[next[i]]）。（不同保持不变，相同则替换）
❽ 数据结构kmp算法中的next函数
我只晓得next
我想你还是不太了解KMP（其实我也不算很懂，尽量说吧O(∩_∩)O~交流下）
那个next其实是T串（字串）自己和自己匹配所得到的。
方法和S T匹配时一样，主不过以前是遇到不匹配时回到NEXT【j】，这个函数中则是遇到不匹配记录下不匹配的位置(说明前面得j个是后面串的后缀)。
至于您说的那个
tvalnext
我不清楚，你能发过来么？一起学习下。O(∩_∩)O~
❾ 求大神给一个KMP算法，C语言的
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
void get_nextval(char const * ptn,int * nextval)
{
int i=0;
nextval[0]=-1;
int j=-1;
int plen=strlen(ptn);
if(ptn==NULL||nextval==NULL)
{
return;
}
while(i<plen)
{
if(j==-1||ptn[i]==ptn[j])
{
++i;
++j;
if(ptn[i]!=ptn[j])
{
nextval[i]=j;
}
else
{
nextval[i]=nextval[j];
}
}
else
{
j=nextval[j];
}
}
}
int kmp_search(char const * src,char const * patn,int const * nextval,int pos)
{
int i=pos;
int j=0;
if(src==NULL||patn==NULL)
{
return -1;
}
int slen=strlen(src);
int plen=strlen(patn);
if(pos<0||pos>slen)
{
return -1;
}
while(i<slen && j<plen)
{
if(j==-1||src[i]==patn[j])
{
++i;
++j;
}
else
{
j=nextval[j];
}
}
if(j>=plen)
{
return i-plen;
}
else
{
return -1;
}
}
int main()
{
char src[]="";
char prn[]="abce";
int * nextval=(int *)malloc(sizeof(int)* strlen(prn));
get_nextval(prn,nextval);
int i=0;
for(i=0;i< strlen(prn);i++)
{
printf("%d",nextval[i]);
}
printf("\n");
printf("the result is:%d\n",kmp_search(src,prn,nextval,5));
return 0;
}
望采纳哦~~O(∩_∩)O~
❿ 请问数据结构的KMP算法这个是什么算出来的
http://blog.csdn.net/ts173383201/article/details/7850120
这里有一篇关于KMP算法不错的分析，我以前收藏的。你可以参考下看看，图文并茂，说明很详细。
希望对你有所帮助。