Tp p; int len;

vector<int> fail;

KMP() {}

KMP(Tp p_) : p(p_), len(p_.size()) {

// @brief 文字列 $p[0:i-1]$ の接頭辞と接尾辞は最大何文字一致する？ (ただし、$|p[0:i-1]|$ 文字未満のみ考慮)

// @brief MP 法に比べ、失敗時の遷移が log 回に改善されている

// @see http://www-igm.univ-mlv.fr/~lecroq/string/node8.html

fail.resize(len + 1, -1);

for(int i=0, j=-1; i<len; i++) {

// その時点で一致しなければ fail[j] 文字以下の一致となる

// j を fail[j] に変更

while(j >= 0 and p[j] != p[i]) j = fail[j];

j++;

fail[i+1] = (i+1 < len and p[i+1] == p[j] ? fail[j] : j);

}

}

// @brief 文字列 $s$ における $p$ の出現位置 (開始位置) のリスト

vector<int> match(Tp s) {

int N = s.size();

vector<int> occur;

for(int i=0, k=0; i<N; i++) {

while(k >= 0 and s[i] != p[k]) k = fail[k];

if(++k == len) {

occur.push_back(i-len+1);

k = fail[k];

}

}

return occur;

}