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)。