題目描述

如題，給出兩個字符串s1和s2，其中s2為s1的子串，求出s2在s1中所有出現(xiàn)的位置。

為了減少騙分的情況，接下來還要輸出子串的前綴數(shù)組next。

（如果你不知道這是什么意思也不要問，去百度搜[kmp算法]學(xué)習一下就知道了。）

輸入輸出格式

輸入格式：
第一行為一個字符串，即為s1

第二行為一個字符串，即為s2

輸出格式：
若干行，每行包含一個整數(shù)，表示s2在s1中出現(xiàn)的位置

接下來1行，包括length(s2)個整數(shù)，表示前綴數(shù)組next[i]的值。

輸入輸出樣例

輸入樣例#1：
ABABABC
ABA
輸出樣例#1：
1
3
0 0 1
說明

時空限制：1000ms,128M

數(shù)據(jù)規(guī)模：

設(shè)s1長度為N，s2長度為M

對于30%的數(shù)據(jù)：N<=15，M<=5

對于70%的數(shù)據(jù)：N<=10000，M<=100

對于100%的數(shù)據(jù)：N<=1000000，M<=1000000

思路：直接把s1接在s2后面進行KMP，枚舉所有點若next[i]==s2.len則i是一個答案。
注意：串接時記得中間加一個符號防止影響結(jié)果（仔細想想）

代碼注釋：
1.字符串都以第0個開始
2.我這里的next[i]表示i點前面（不包含i）最長的前綴和后綴相同的字符串如：”abcabc”中 s[3]=’a’,next[3]=0,s[4]=’b’,next[4]=1(‘a(chǎn)’),s[5]=’c’,next[5]=2(“ab”)。
3.不明白KMP的可以嘗試根據(jù)代碼手算個數(shù)據(jù)體會一下（最好是畫線段或矩形分情況思考一下），我不具體寫了。

code1:

//By Menteur_Hxy #include<cstdio> #include<iostream> #include<algorithm> #include<cstring> using namespace std;const int MAX=100005; int next[MAX]; char s[MAX],a[MAX];int main() {scanf("%s",s+1);getchar();int len1=strlen(s+1);scanf("%s",a+1);int len2=strlen(a+1);int len=len2;a[++len]='*';for(int i=1;i<=len1;i++) a[++len]=s[i];for(int i=2,j=0;i<=len;i++) {while(j && a[i]!=a[j+1]) j=next[j];if(a[i]==a[j+1]) j++;next[i]=j;}for(int i=1;i<=len;i++) if(next[i]==len2) printf("%d\n",i-2*len2);for(int i=1;i<=len2;i++) printf("%d ",next[i]);return 0; }

code2:

//By Menteur_Hxy #include<cstdio> #include<iostream> #include<cstdlib> #include<algorithm> #include<cstring> #include<cmath> #include<ctime> using namespace std;const int MAX=1000005; int next[MAX<<1]; string s1,s2;int main() {cin>>s1;getchar();cin>>s2;int len1=s1.length();int len2=s2.length();int len3=len1+len2+1;s2+='#'+s1;//'#'即隔離符號next[0]=-1;int k=-1,j=0;while(j < len3) {if(k==-1 || s2[j]==s2[k]){//若k位于字符串首前或s[k]==s[j]顯然有k++,j++;next[j]=k;}else k=next[k];//向前尋找一個小一點的但又可能滿足條件的最大的}for(int i=0;i<len3;i++) if(next[i]==len2) printf("%d\n",i-len2*2);for(int i=0;i<len2;i++) printf("%d ",next[i+1]);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/Menteur-Hxy/p/9248018.html

與50位技術(shù)專家面對面20年技術(shù)見證，附贈技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的P3375 【模板】KMP字符串匹配 （KMP模板）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。