❶ 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演算法不錯的分析，我以前收藏的。你可以參考下看看，圖文並茂，說明很詳細。
希望對你有所幫助。