- 【用途】字串匹配
- 給兩個字串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;
}