模板】KMP字串匹配
KMP字串匹配用于兩個字串中，是否一個字串是另一個的子串
我們稱其中兩個串一個為S(長度為n)，一個為P（長度為m），問是否P為S的字串
這種題暴力的想法很容易想到但時間復雜度為\(O(nm)\)
其實KMP也就只是在暴力的想法上進行了優化，不過優化的程度很高
舉例
S：a b a d a b a
P: a b b
暴力思路就是列舉主串的每個字符，然后從列舉到的字符后m個字符是否有一樣即可
而暴力的思路明顯存在缺點，一旦匹配失敗就只右移一位，然后從頭繼續匹配
而KMP的思路是移動多位（那么此時同學會想，移動多位會不會丟失一些可能可以匹配的字串?且接著往下看）
這個疑問非常有道理，所以KMP的演算法妙就妙在這里，跳過一些不可能匹配成功的位置
這個問題被很好的解決，通過next陣列
next[i]陣列存盤的是以P[0~i]為字串的以長度為k的前綴和后綴相等，k取最大（k<=i）(長度不能等于i+1,因為如此自己便等于自己，自己等于自己無意義)
簡而言之，最長同前綴后綴
假如匹配到某個位置\(x（x<m）\)
即\(S[l~r]=P[0~x]\)
但是\(S[r+1]!=P[x+1]\)
按暴力的演算法我們會想去從頭開始匹配
例如
\(S[l+1]==P[0]\)
但我們發現其實\(S[l\) ~ \(r]=P[0\) ~ \(x]\)這一段是匹配過的
如果存在\(S[l~r]\)中某一段\([l'\) ~ \(r']\)等于某一段\([h\) ~ \(t]\)，就可以使$ P[0 $~ \(r'-l']=S[h\) ~ \(t]\)
同時從其他地方開始匹配也絕無可能,這樣就能大大降低復雜度
你會發現前面引入的next陣列完美解決了上述問題，
最長同長度前后綴滿足某段等于某段，而且最長的前后綴，使得其他地方也不存在匹配成功的可能（很好的思考題，這里的原因）
- 證明（非嚴謹）
如果存在 $P[0 $ ~ $ x]=S[r-x+1$ ~\(r]\)且不是最長同前綴后綴，那么x一定小于最長同前綴后綴的長度
next陣列求法
也有暴力求法，但時間復雜度為\(O(m^2)\),違背了我們降低演算法復雜度的初心
你想想\(next[i]\)與\(next[i-1]\)有沒有聯系
如果\(P[next[i-1]]=P[i]\),顯然\(next[i]=next[i-1]+1\)
如果≠，存在\(P[0~next[i-1]]=p[i-1-next[i-1]~i-1]\)
所以存在$P[0 $~ \(next[ next[ i-1 ] ]-1 ]=P[ next [ i-next[ i-1 ]-1\) ~ \(i-1]]\)
這時沿用上述的思路 如果\(P[next[i-1]]=P[i],\)也可以\(next[i]=next[next[i-1]]+1\)
否則，我們可以繼續是否存在\(next[next[next[..]]]\)是成立,直到\(next[next[...]]=0\)
- code
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=1e6+10;
char a[maxn],b[maxn];
int nex[maxn]={0};
int top=0;
int main(){
ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
cin>>(a+1)>>(b+1);
int lena=strlen(a+1),lenb=strlen(b+1);
for(int i=2,j=0;i<=lenb;++i){
while(b[i]!=b[j+1] && j) j=nex[j];
if(b[j+1]==b[i]) ++j;
nex[i]=j;
}
for(int i=1,j=0;i<=lena;++i){
while(j&& b[j+1]!=a[i]) j=nex[j];
if(b[j+1]==a[i]) ++j;
if(j==lenb) {
cout<<i-lenb+1<<endl;
j=nex[j];
}
}
for(int i=1;i<=lenb;++i) cout<<nex[i]<<" ";
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/296238.html
標籤：其他