KMPのK - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ
ここを参考にさせてもらいました。
KMPで求めるのはまさに蟻本p327「禁止文字列」における文字列の状態推移である。
すなわち、ある文字列TとSを比較するとして、Sのi番目でマッチングが失敗したとき、次にどこを見るかを線形時間で求めてくれる。
MPよりも高速。
実はMPに少し手を加えるだけでKMPになる。
vector<int> KMP(string S) { int n = (int)S.size(); S += '_'; vector<int> A(n + 1); A[0] = -1; int j = -1; rep(i, 0, n) { while (j >= 0 && S[i] != S[j]) j = A[j]; j++; if(S[i + 1] == S[j]) A[i + 1] = A[j]; else A[i + 1] = j; } return A; }
if(S[i + 1] == S[j]) A[i + 1] = A[j]というのが新しく追加された行だが、S[i + 1]でマッチングが失敗したら、S[i+1]とS[j]は同じ文字なのでS[j]でもマッチングが失敗するからA[j]に移動していいという理屈である。
これによってループ一回あたりO(logK)が達成される。詳しくは上のsnukeさんのブログを参照のこと。
これで何が嬉しいかというと、MP法では「禁止文字列」の下処理がO(K^2)かかっていたが、KMP法ではO(KlogK)となる。
"AACAACAA"みたいな文字列でMP法とKMP法で得られるAを比較してみると、
MP: {-1, 0, 1, 0, 1, 2, 3, 4, 5, 2}
KMP:{-1,-1, 1,-1,-1, 1,-1,-1, 5, 2}
となっており、KMPの方が圧倒的に優秀なことがわかる。
以下はKMP法による「禁止文字列」の下処理
vector<int> A = KMP(S); rep(i, 0, K) { rep(j, 0, 4) { if(S[i] == AGCT[j]) nex[i][j] = i + 1; else { int k = A[i]; while(k >= 0 && S[k] != AGCT[j]) k = A[k]; k++; nex[i][j] = k; } } }
下処理自体はMP法と変わらない。
がんばっても線形にはならない気がするんだけどどうなんだろう…