［アルゴリズム］KMPアルゴリズム

📌 Brute-force Algorithm

これは文字列マッチングアルゴリズムを最も簡単に実現したものである.

int BruteForceMatch(string text, string pattern)
{
	for (int i = 0; i <= text.size() - pattern.size(); i++)
	{
		int j = 0;
		while (j < pattern.size() && text[i + j] == pattern[j])
			j++;

		// match at i
		if (j == pattern.size())
			return i;
	}

	return -1;
}

時間の複雑さは、テキストの長さとPatternの長さの積です.
単純比較アルゴリズムの時間的複雑さ:O(NM)

📌 Knuth-Morris-Pratt Algorithm

KMPアルゴリズムと呼ばれる文字列マッチングアルゴリズム.KMPアルゴリズムは,パターンを文内で左から右に比較し,Bret-forceアルゴリズムとは異なり,パターンの位置をより効率的に移動させることができる.パターンと文が一致しない場合は、繰り返し演算をできるだけ避け、パターンを右に移動します.そのため,文に不一致が生じた場合,どれだけスキップしたかを判断して比較演算を行う必要がある.

KMPアルゴリズム比較例

これを判断するには、ナビゲーション文字列の接頭辞と接尾辞の最大一致部分を知る必要があります.このためには、次の手順が必要です.

📌 Failure Function

KMPアルゴリズムでは,プローブ文字列の接頭辞と接尾辞の一致部分を計算することにより,配列の形で格納される関数である.複数の名前と呼ばれていますが、本稿では失敗関数(failure function)と呼びます.失敗した関数を求めるプロセスは次のとおりです.

比較するナビゲーション文字列部分では、接頭辞と接尾辞の両方を持つ最大文字列を求め、配列の形で格納します.

失敗した関数で計算される配列は次のとおりです.計算された配列を参照してナビゲーション文字列を移動します.一致しないインデックスがjである場合、ナビゲーション文字列の位置をF(j-1)インデックスに配置して次の比較を行います.

Failure関数コードの例

void FailureFunction(string pattern)
{
	F[0] = 0;
	int i = 1;
	int j = 0;

	while (i < pattern.size())
	{
		if (pattern[i] == pattern[j])
		{
			F[i] = j + 1;
			i++;
			j++;
		}
		else if (j > 0)
			j = F[j - 1];
		else
		{
			F[j] = 0;
			i++;
		}
	}
}

失敗関数の形式はKMPアルゴリズムの形式と大きく異なる.失敗した関数のコードから,反復文におけるi indexは1増加するごとにi−jの値は少なくとも1増加する.したがって,最悪の場合でもプローブ文字列の2倍を超えることはないので,失敗関数の実行時間はO(M)に収束すると考えられる.
失敗関数の時間的複雑さ:O(M)

📌 KMPアルゴリズム分析

KMPアルゴリズムコード例

int KMPmatch(string text, string pattern)
{
	int n = text.size();
	int m = pattern.size();
	FailureFunction(pattern);

	int i = 0;
	int j = 0;
	while (i < n)
	{
		if (text[i] == pattern[j])
			if (j == m - 1)
				return i - j;
			else
			{
				i++;
				j++;
			}
		else
		{
			if (j > 0)
				j = f[j - 1];
			else
				i++;
		}
	}

	return -1;
}

KMPアルゴリズムコードの繰り返し文では、iが1増加するごとに、i−jの値は少なくとも1増加する.したがって,反復が文字列サイズの2倍を超えないため,KMPアルゴリズムの実行時間は失敗関数の実行時間にO(N+M)を加えることに収束する.
KMPアルゴリズムの時間複雑度:O(N＋M)

📌 の最後の部分

今日,文字列ナビゲーションアルゴリズムにおける性能に優れたKMPアルゴリズムについて詳細に説明した.KMPアルゴリズムは文字列検索においてほとんど最適な性能であるため,符号化テストにおいてもしばしば出現し,他の文字列検索アルゴリズムを学習する上でも重要である.KMPアルゴリズムに最初に触れた人であれば、この文書が役に立つことを願っています.