寫在前面：博主是一位普普通通的19屆雙非軟工在讀生，平時最大的愛好就是聽聽歌，逛逛B站。博主很喜歡的一句話花開堪折直須折，莫待無花空折枝：博主的理解是頭一次為人，就應該做自己想做的事，做自己不后悔的事，做自己以后不會留有遺憾的事，做自己覺得有意義的事，不浪費這大好的青春年華。博主寫博客目的是記錄所學到的知識并方便自己復習，在記錄知識的同時獲得部分瀏覽量，得到更多人的認可，滿足小小的成就感，同時在寫博客的途中結交更多志同道合的朋友，讓自己在技術的路上并不孤單。

目錄:
1.模式串從下標1開始的next數組求解
???? ?? 數據結構嚴蔚敏版
???? ?? 日常算法題版
2.模式串從下標0開始的next數組求解
???? ?? 模板1
???? ?? 模板2
3.模式串與主串的匹配
???? ?? 數據結構嚴蔚敏版
???? ?? 日常算法題版

1.模式串從下標1開始

1.1數據結構嚴蔚敏版

這個版本是官方標配版，第i個位置的next數組值的意義是：前i-1個字符的最大真公共前后綴的長度加1，加1的目的是下一次主串與模式串失配時模式串要跳到的位置。比如我們一個字符串abab那么它在此處的next數組值為0112;

void get_next(char T[],int next[]) {int i=1;int j=0;next[1]=0;while(i<T[0])//T[0]為字符串長度{if(j==0||T[i]==T[j])//T[i]表示后綴的單個字符，T[j]表示前綴的單個字符 {i++;j++;next[i]=j; }elsej=next[j];//若字符不相同那么j值回溯 } }

1.1日常算法題版

有的時候，模式串需要我們手動的輸入，我們可以選擇從1開始輸入字符串，然后求得此模式串的next數組值(注：kmp代表next數組),這個與嚴蔚敏版不同的是第i個位置的next數組值是前i個字符的最大真公共前后綴長度，比如字符串abab在此段代碼中next數組值為0012

cin>>str+1;//從數組下標為1開始輸入int len=strlen(str+1);int j=0;for(int i=2;i<=len;i++){while(j>0&&str[j+1]!=str[i])j=kmp[j];if(str[j+1]==str[i])j++;kmp[i]=j; }

2.模式串從下標0開始

2.日常算法題版本

int j = 0;next[0] = 0;for(int i = 1; i < s.size(); i++) { while (j > 0 && s[i] != s[j]) { j = next[j - 1]; }if (s[i] == s[j]) { j++;}next[i] = j; }

3.模式串與主串的匹配

3.1數據結構嚴蔚敏版

int Index_KMP(String S, String T, int pos){// i 用于主串S當前位置下標值，若pos不為1，則從pos位置開始匹配int i=pos;//j 用于子串T中當前位置下標值int j=1;// 定義next數組int next[255];// 對串T作分析，得到next數組get_next(T,next);// 若i小于S的長度且j小于T的長度時，循環繼續while(i<=S[0] && j<=T[0]){// 兩字母相等則繼續，相對于樸素算法增加了// j=0 判斷if(j==0||S[i]==T[j]){++i;++j;}// 指針后退重新開始匹配else{// j退回合適的位置，i值不變j=next[j];}}if(j>T[0]){return i-T[0];}elsereturn 0; }

3.2算法題版（對應模式串從下標0開始的兩個模板）

int j = 0;for (int i = 0; i < haystack.size(); i++) { while(j > 0 && haystack[i] != needle[j]) { j = next[j - 1]; }if (haystack[i] == needle[j]) { j++;}if (j == needle.size() ) { return (i - needle.size() + 1);}}

總結

以上是生活随笔為你收集整理的KMP算法求解next数组值(模式串从下标0开始或从下标1开始)以及求值后与主串的匹配过程的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。