字符串模式匹配(一)——單模匹配(KMP)

單模匹配的常用算法為KMP，多模匹配常用算法為AC自動機。

暴力匹配法(BF,$O(|S|\times |T|)$)

設(shè)源串$S$的匹配指針為$i$，模式串$T$的匹配指針為$j$。暴力法通過逐個比較$S$與$T$中的每個字符進行模式匹配。

算法流程：循環(huán)執(zhí)行下列步驟，直到$i$越界，匹配結(jié)束：

• 若$S[i]=T[j]$，該點成功匹配，繼續(xù)比較。若$j$越界則為成功匹配，j=0進行下次匹配。
• 若$S[i]\ne T[j]$，則為二者的失配點，回溯二者的匹配指針。二者在失配前均為成功匹配，匹配指針一直同步變化，$j$為相對于匹配開始點的增量，因此本輪匹配起點即為$i?j$。$i$回溯到起點的下一個位置i=i-j+1，j=0。

string s,t;
vector<int>ans;//記錄所有成功匹配開始點下標
void bf(){
    int i=0,j=0;
    while(i<s.size()){
        if(t[j]==s[i]){
            i++,j++;
            if(j>=t.size()) ans.push_back(i-t.size()),j=0;//j越界則產(chǎn)生答案
        }else i=i-j+1,j=0;//匹配失敗,回溯
    }
}

KMP($O(|S|+|T|)$)

KMP是在BF上進行改進的單模匹配算法，其主要改進是最長公共前后綴數(shù)組，以避免大量的非必要回溯。

大量回溯的不必要性

設(shè)源串$S$的匹配指針為$i$，模式串$T$的匹配指針為$j$。設(shè)當(dāng)前輪匹配的失配點前，$S$中成功匹配部分為其子串$S^{\prime }$，$T$中成功匹配部分為其前綴$T^{\prime }$，$S^{\prime }$與$T^{\prime }$完全相同。

• 若$T^{\prime }$中每個字符都不同：失配時暴力法的回溯為i=i-j+1，j=0，但$i$的回溯是完全不必要的。由于$T^{\prime }$中每個字符都不同，因此S[i-j+1]也不可能與T[0]相同。$i$不動，j=0即可。
• 若$T^{\prime }$中有部分字符相同，且相同部分為$T^{\prime }$的長度為$L$的前綴和后綴：$S^{\prime }$也具有等長的相同前后綴，因此$T^{\prime }$前綴與$S^{\prime }$后綴已經(jīng)匹配，這部分無需重復(fù)匹配。失配時$i$不動，$j$移動到$T^{\prime }$前綴的下個位置L繼續(xù)匹配即可。
• 若$T^{\prime }$中部分字符相同，且相同部分并非$T^{\prime }$的前綴和后綴：此種情況等價于$T^{\prime }$中每個字符都不同。$i$不動，j=0即可。
  
  由此可得，$i$完全沒有必要回溯，只對$j$回溯即可。

最長公共前后綴數(shù)組

定義數(shù)組$Next[j]$，設(shè)模式串$T$的前$j?1$個字符構(gòu)成其前綴$T^{\prime }$，則$Next[j]$存儲$T^{\prime }$的前綴與后綴的最長交集長度(注意此處均指不包含$T^{\prime }$自身的真前后綴)，則$T^{\prime }$的后綴中最后下標為$j?1$，$T^{\prime }$前綴中最后下標為$Next[j]?1$(公共長度-1，注意字符串下標從$0$開始)，代表當(dāng)失配時，$j$所回溯的位置。

• 若$T[i]=T[j]$，則$[0,i]$的長度轉(zhuǎn)移自$[0,i?1]$的長度并$+1$。$Next[i+1]=Next[i]+1$。
• 若$T[i]\ne T[j]$，則前綴與后綴失配，屬于回溯分析中的情況3，后綴失去后綴特性，無法在KMP中用于直接跳躍，$j$回溯。$Next[i+1]=0,j=Next[j]$。

獲取最長公共前后綴數(shù)組的本質(zhì)：模式串本身在進行自我模式匹配。

string s,t;//下標從0開始
vector<int>Next,ans;//注意next是cpp的關(guān)鍵字
void getNext(){//本質(zhì):模式串在進行自我模式匹配
    Next.resize(t.size()+1);
    Next[0]=0,Next[1]=0;//Next[0]不用;由于在找真前后綴的最長交集長度,因此Next[1]為0
    for(int i=1;i<t.size();i++){
        int j=Next[i];
        while(j&&t[i]!=t[j]) j=Next[j];//j在失配點跳躍到Next[j]
        if(t[i]==t[j]) Next[i+1]=j+1;//[0,i]的答案轉(zhuǎn)移自[0,i-1]+1
        else Next[i+1]=0;//后綴失去后綴特性
    }
}
void kmp(){
    getNext();
    int j=0;
    for(int i=0;i<s.size();i++){
        while(j&&s[i]!=t[j]) j=Next[j];//j在失配點跳躍到Next[j]
        if(s[i]==t[j]) j++;
        if(j==t.size()) ans.push_back(i+1-t.size());//j越界,則匹配成功
    }
}