【筆記】KMP (Knuth–Morris–Pratt algorithm)

  • 【用途】字串匹配
    • 給兩個字串s,t,計算 t 在 s 的 substring 中出現的位置(次數)
  • 【做法1】枚舉起點,暴力比對,複雜度 O( s.size() * t.size() ) (TLE)
  • 【做法2】KMP (Knuth–Morris–Pratt algorithm)
    • 先對字串 t 做預處理,減少許多冗余的字元比對
    • 複雜度 O( s.size() + t.size() )
  • 【預處理】Failure function 共同前後綴
    • failure function:若比到此位置才失敗,下一個可以繼續嘗試的位置
    • 【例】a  a  b  a  a  c  a  a  b  a  a  c  d
    • 【例】-1 0 -1 0  1  -1 0 1  2  3  4  5  -1 以此位置結尾的substring 對整個字串的前綴最長可匹配到哪個位置
  • 比對失敗時,對該位置的 failure function 繼續嘗試,複雜度為:
    • 比對成功,位置向後推一格
    • 比對失敗,可能需要查多次 failure 直至推至 -1
    • 因為位置一次只能向後推一格,失敗的次數最多和字串長度相同
  • 【練習】HDU 1867 A + B for you again
  • 【練習】HDU 2203 亲和串題解
  • 【練習】HDU 3336 Count the string題解

【實作】 build Failure function

vector<int> build(string &t) {
    vector<int> F(t.size());
    F[0] = -1;
    
    for (int i = 1, pos = -1 ; i < t.size() ; i++) {
        while (~pos && t[i] != t[pos + 1])
            pos = F[pos];

        if (t[i] == t[pos + 1])
            pos++;

        F[i] = pos;
    }
    return F;
}

【實作】 match

bool match(string &s, string &t, vector<int> &F) {
    for (int i = 0, pos = -1 ; i < s.size() ; i++) {
        while (~pos && s[i] != t[pos + 1])
            pos = F[pos];

        if (s[i] == t[pos + 1])
            pos++;
        
        if (pos + 1 == (int)t.size())
            return true;
    }
    return false;
}
分享本文 Share with friends