KMP法

KMPのK - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ

MP法とKMP法の違い - 生きたい

ここを参考にさせてもらいました。

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法と変わらない。
がんばっても線形にはならない気がするんだけどどうなんだろう…