假如str的前j個字元是前i個字元的字尾(j<i),那麼next[i]就是所有這樣的j的最大值形象地說,就是假如第i+1個字元匹配失敗之後,下一個可能匹配位置至少應該往後挪動多少就"abaabc"而言next[1]=0next[2]=0next[3]=1next[4]=1next[5]=2next[6]=0計算過程基本上抄自演算法導論,假設str長度為nk=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);}對照著後面這一段很容易理解第一段
假如str的前j個字元是前i個字元的字尾(j<i),那麼next[i]就是所有這樣的j的最大值形象地說,就是假如第i+1個字元匹配失敗之後,下一個可能匹配位置至少應該往後挪動多少就"abaabc"而言next[1]=0next[2]=0next[3]=1next[4]=1next[5]=2next[6]=0計算過程基本上抄自演算法導論,假設str長度為nk=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);}對照著後面這一段很容易理解第一段