題目描述

• 給定一個字符串S，以及一個模式串P，所有字符串中只包含大小寫英文字母以及阿拉伯數字。
• 模式串P在字符串S中多次作為子串出現。
• 求出模式串P在字符串S中所有出現的位置的起始下標。

輸入格式

• 第一行輸入整數N，表示字符串P的長度。
• 第二行輸入字符串P。
• 第三行輸入整數M，表示字符串S的長度。
• 第四行輸入字符串S。

輸出格式

• 共一行，輸出所有出現位置的起始下標（下標從0開始計數），整數之間用空格隔開。

數據范圍

• 1 ≤ N ≤ 10^5
• 1 ≤ M ≤ 10^6

基本思路

• KMP算法是一個經典的字符串匹配算法。字符串匹配如果使用蠻力算法實現，則最壞情況下的時間復雜度是O(m*n)，其中m和n分別是母串和子串的長度；KMP算法將該時間復雜度優化到了O(m+n)，可以說實現了一個重大的飛躍。
• KMP算法可以分為求next數組和基于next數組的字符串匹配兩部分，其中前一部分會更加困難一些。
• 在字符串匹配部分，采用的方法是一種雙指針算法，兩個指針分別指向母串和子串中的一個待匹配字符。每次都比較兩個指針所指向的字符，如果字符相同（發生匹配的情況），則同時將指針移動到下一個位置；如果字符不同（發生失配的情況），則進行分情況討論：
  • 對于子串的首字符失配，則直接將母串的指針移動到下一個位置；
  • 對于子串的非首字符失配，則根據已經得到的next數組，修改子串指針所指向的位置，避免從頭開始匹配帶來的冗余消耗。
• next數組的求解是KMP算法最困難的部分，下面進行介紹：
  • next數組中的每一個元素的值，表示從字符串的首個字符開始到當前元素對應的字符結束所構成的子串的最長相同前后綴的長度。注意，這里的最長相同前后綴不包含字符串本身。
  • next數組的首元素需要手動進行初始化，設置其值為0。
  • next數組的構建同樣是基于雙指針算法完成的。起初，分別設置兩個指針指向字符串的第一個字符和第二個字符，之后這兩個指針都會向后移動。
    • 當兩個指針指向的字符相同時，則當前右指針對應的字符的next數組元素值就是在上一個元素的next數組元素值上自增1；
    • 當兩個指針指向的字符不同時，則說明當前的最長相同前后綴分別加上左右指針所指向的字符后，無法繼續構成相同的前后綴，因此就需要嘗試尋找更短子串構成最長相同前后綴，即代碼中的prefix_length = ne[prefix_length - 1]部分。這一部分理解起來比較復雜，因此下面通過一個實例進行介紹。
    • 假設需要構建對應的next數組的字符串是ABACABAB，且當前已經完成匹配的部分是第一個到第三個字符ABA和第五個到第七個字符ABA，第七個字符A對應的next數組值是3。現在左指針指向了第四個字符C，右指針指向了第八個字符B，顯然兩者不同，因此左右兩邊的字符串增加了新字符后，ABAC和ABAB顯然不是相同的前后綴，因此我們需要使用別的方式計算由這八個字符構成的字符串的最長相同前后綴。
    • 直觀上我們發現，如果需要構建最長相同前后綴，那么就需要兩個條件：加入的新字符完全相同、加入新字符前的前綴和后綴完全相同。這樣，就可以產生一個巧妙的構思：既然當前字符串的最長相同前后綴分別增加一個新字符后無法繼續構成最長相同前后綴，那么我們能不能退而求其次，不是使用當前的最長相同前后綴，而是第二長相同前后綴，來構建下一個最長相同前后綴呢？這是因為，第二長相同的前后綴也滿足加入新字符前的前綴和后綴完全相同，并且修改了前綴和后綴后，前綴的下一個字符也會隨著前綴更改一次，說不定就可以和右指針新插入的字符相同了。
    • 例如，對于ABACABA，最長的相同前后綴是ABA（前三個字符和后三個字符），但是最長的相同前后綴再增加第八個字符B后，構成的前后綴分別是ABAC和ABAB，顯然不相同。但是，如果使用第二長前后綴A（即第一個字符和第七個字符），增加一個字符B后，仍然可以構成相同前后綴AB。因此，在字符串當前的最長相同前后綴無法繼續構成下一步的最長相同前后綴時，我們可以使用第二長的相同前后綴繼續進行嘗試，如果還不行則使用第三長的相同前后綴…直到找到可以繼續構成相同前后綴的相同前后綴或確定不存在可以構成相同前后綴的相同前后綴（因為一個字符串的相同前后綴的個數是有限的）。現在的問題就是如何找出一個字符串的第二長相同前后綴。
    • 對于字符串ABABABA，其最長相同前后綴是ABA，包含三個字符，那么第二長的相同前后綴如果存在，則一定只包含兩個字符或者一個字符，所以我們需要比較該字符串的前兩個字符和后兩個字符，以及第一個字符和最后一個字符。由于我們已經知道了ABA是最長相同前后綴，所以后兩個字符實際上就是第二個和第三個字符，最后一個字符實際上就是第三個字符，因此問題就轉換為了比較該字符串的前兩個字符和第二個第三個字符，以及字符串的第一個字符和第三個字符是否相同的問題，其實也就是前三個字符構成的字符串ABA的最長相同前后綴問題！
    • 由于我們求解next數組的過程是順序進行的，因此我們已經計算出了前三個字符ABA對應的next數組元素分別為001，因此我們可以得出對于ABA，其最長相同前后綴的長度為1，因此對于字符串ABABABA，其第二長相同前后綴的長度也是1。因此，在最長相同前后綴ABA無法繼續構成最長相同前后綴時，我們使用第二長的相同前后綴嘗試繼續構建最長相同前后綴，構建出了AB，成功！

實現代碼

#include <iostream>
using namespace std;// 創建一個靜態數組ne作為next數組
const int n = 1e5 + 10;
int ne[n];// 獲取next數組的函數
// 傳入的參數分別是字符串的長度N和字符串P
// 函數根據傳入的參數計算next數組
void get_next(int N, const string& P)
{// 首先將第一個元素對應的next值設置為0ne[0] = 0;// 定義并初始化兩個指針int prefix_length = 0, j = 1;// 通過循環的方式求解next數組，直到完成對字符串的遍歷while(j < N){// 情況1：兩個指針所指向的字符相同，則說明最長相同前后綴可以同時自增，并記錄結果if(P[prefix_length] == P[j]){++ prefix_length;ne[j] = prefix_length;++ j;}else{// 情況2：兩個指針所指向的字符不同且第一個指針并不是指向字符串首字符，則根據next數組找出次最長相同前后綴if(prefix_length != 0) prefix_length = ne[prefix_length - 1];// 情況3：兩個指針所指向的字符不同，且第一個指針指向字符串首元素，則直接將此處記錄為0即可else{ne[j] = 0; ++ j;}}}
}// 進行KMP字符串匹配的函數
// 傳入的參數分別是子串的長度N、子串P、母串的長度M、母串S
// 函數會在控制臺輸出子串P在母串S中所有出現位置的首字符下標
void KMP_search(int N, const string& P, int M, const string& S)
{// 首先根據子串P獲取其對應的next數組get_next(N, P);// 定義并初始化母串和子串的指針int pp = 0, sp = 0;// 通過循環進行字符串匹配，當超出母串長度時停止循環while(sp < M){// 情況1：當前母串和子串的對應字符相同，則指針同時自增比較下一個元素if(P[pp] == S[sp]) {++ pp; ++ sp;}else{// 情況2：當前母串和子串的對應字符不同，且不是發生在子串第一個元素，則基于next數組修改子串指針if(pp != 0) pp = ne[pp - 1];// 情況3：當前母串和子串的對應字符不同，且發生在子串的第一個元素，則直接將母串指針自增else ++ sp;}// 每一次當子串遍歷完成一次，則輸出一次出現下標，并基于next數組修改子串指針if(pp == N){cout << sp - pp << " ";pp = ne[pp - 1];}}
}int main(void)
{int N, M;string P, S;cin >> N >> P >> M >> S;KMP_search(N, P, M, S);return 0;
}