KMP算法

應用場景

• KMP算法一般用於字符串匹配問題
• 例如：給出兩個字串S，P需要判斷P串是否為S串的子串

前綴表

• 前綴：包含第一個字符不包含最後一個字符
• 後綴：包含最後一個字符不包含最後一個字符
  例如：aaba
  前綴分別為：a, aa, aab
  後綴分別為：a, ba, aba
• 最長相等前後綴：記錄前綴和後綴相等的長度，在這個例子中最長相等前後綴為a，長度為1
• 在KMP算法當中，用一個next數組記錄每個字符的最長相等前後綴
  例如：aabaa
  前綴分別為：a, aa, aab, aaba
  後綴分別為：a, aa, baa, abaa
  next數組為：a:0, aa:1, aab:0, aaba:1, aabaa:2
  next = [0, 1, 0, 1, 2]

前綴表在KMP算法中的作用

• 暴力解法中，我們需要兩重循環遍歷P串和S串，直到找到匹配的字串，時間複雜度為O(n*m)，n，m分別表示P串和S串的長度
• KMP算法的核心思想就是用前綴表記錄已經匹配過的文本內容，使得當發生匹配衝突的時候，可以不需要重新遍歷，而是通過前綴表回退到之前匹配成功過的位置繼續匹配，next數組就是前綴表
• 具體原理參考https://www.bilibili.com/vide...

next數組的實現（前綴表實現）

• 構造next數組分為四步：
• 初始化
  定義兩個指針i，j
  j指向前綴末尾位置，i指向後綴末尾位置
  next數組初始化為0，j從0開始，i從1開始
• 處理前後綴不相同的情況
  當前後綴不相等並且j>0時（後續要回退到j-1的狀態所以要保證j>0）
  j回退到j-1的狀態
• 處理前後綴相同的情況
  前後綴相同時，j向後移動一位
• 更新next數組
  將next數組更新為j

• 代碼模板

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

leetcode.28

• 鏈接https://leetcode.cn/problems/...

• leetcode解題代碼

  class Solution {
  public:
    int strStr(string haystack, string needle) {
        int n = haystack.length(), m = needle.length();
        vector<int> next(m);
        int j = 0;// 初始化j
        next[0] = 0;// 初始化next數組
        for (int i = 1; i < m; i ++){// 初始化i
            while (j > 0 && needle[i] != needle[j]) j = next[j - 1];// 前後綴不相同時
            if (needle[i] == needle[j]) j ++;// 前後綴相同時
            next[i] = j;// 更新next數組
        }
  
        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);
            }
        }
        return -1;
    }
  };

leetcode.459

• 鏈接https://leetcode.cn/problems/...

• leetcode解題代碼

  class Solution {
  public:
    bool repeatedSubstringPattern(string s) {
        int n = s.size();
        vector<int> next(n);
        int j = 0;
        next[0] = 0;
        for (int i = 1; i < n; i ++){
            while (j > 0 && s[i] != s[j]) j = next[j - 1];
            if (s[i] == s[j]) j ++;
            next[i] = j;
        }
        return next[n - 1] != 0 && n % (n - next[n - 1]) == 0;
    }
  };

字符串前綴哈希

應用場景

• 求兩個字符串的子串是否相同

應用方法

• 字符串的映射
  例如：有一個'abcdefgycr'的字符串，將其映射成某個哈希值並用數組h存下來
  h[n]表示字符串第n位的哈希值
  h[0]=0，h[1]='a'的哈希值，h[2]='ab'的哈希值...
• 哈希值的定義
  例如：字符串'abcd'的哈希值是多少呢？
  我們把'abcd'看成p進制的數，那麼'abcd'則可以表示為
  a*p^3+b*p^2+c*p^1+d*p^0
  但是這樣映射的值可能過大，所以我們再將其取模q
  這樣就可以將字符串映射到0~q-1之間
  一般情況下p=131，q=2^64，可以假定不會發生哈希衝突>.<（感興趣的可以查一下）
• 定義一個區間[L, R]的哈希值
  通過上述方式我們已經知道了h[L-1]和h[R]
  通過h[R] - h[L-1]*p^(R-L+1)

實現方法

typedef unsigned long long ULL;// 可以省略取模的步驟了

const int P = 131;

ULL h[N], p[N];

// 初始化
p[0] = 1;// p^0 = 1
h[0] = 0;
// 前綴和定義前綴字符串哈希
for (int i = 1; i <= n; i ++){
    h[i] = h[i - 1] * P + str[i];
    p[i] = p[i - 1] * P;
}
// 計算字串[L, R]的哈希值
ULL get(int l, int r){
    return h[r] - h[l - 1] * p[r - l + 1];
}

leetcode.796

• 鏈接https://leetcode.cn/problems/...
• 解題思路：求兩個字符串的哈希值，比較對應段是否相等
  為了不用求解兩次字符串哈希，可以將兩個字符串拼接

• leetcode解題代碼

  typedef unsigned long long ULL;
  
  const int N = 210, P = 131;
  ULL h[N], p[N];
  
  class Solution {
  public:
    ULL get(int l, int r) {
        return h[r] - h[l - 1] * p[r - l + 1];
    }
  
    bool rotateString(string A, string B) {
        if (A.size() != B.size()) return false;
        string s = ' ' + A + B;
        int n = s.size() - 1;
        p[0] = 1;
        for (int i = 1; i <= n; i ++ ) {
            p[i] = p[i - 1] * P;
            h[i] = h[i - 1] * P + s[i];
        }
  
        for (int k = 1; k < A.size(); k ++ )
            if (get(1, k) == get(n - k + 1, n) && get(k + 1, A.size()) == get(A.size() + 1, n - k))
                return true;
        return false;
    }
  };

  解題參考：https://www.acwing.com/
  刷題順序參考：https://www.programmercarl.com/