---
tags: algorithm,dp,string
---
# KMP(Knuth–Morris–Pratt algorithm)
## 1. 解決的問題
字串str1和str2，str1是否包含str2，如果包含返回str2在str1中開始的位置。

## 2. 作法
先求 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 對整個字串的前綴最長可匹配到哪個位置

接著處理時有3種情況
(1) 比對成功，位置向後推一格
(2) 比對失敗，可能需要查多次 failure 直至推至 -1

## 3.實作
s為小字串 t為大字串
Failure function

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

match

vector<int> KMP_match(string s,string t,vector<int> F){
    vector<int> ans;
    for (int i = 0, pos = -1 ; t[i] ; i++) {
        while (pos!=-1 && t[i] != t[pos + 1]){
            pos = F[pos];
        }
        if (t[i] == t[pos + 1]){
            pos++;
        }
        if(!s[pos+1]){    //s[pos+1]!="\0"
            ans.push_back(i-p);
            pos=F[pos];
        }
    }
    return ans;
}