(JohnZero)C+:KMPアルゴリズム

KMPアルゴリズム

概要

図解例

コード

概要
kmpアルゴリズムが完了するタスクは,2つの文字列Oとfを与え,長さはそれぞれnとmであり,fがOに現れるか否かを判断し,現れると現れる位置を返すことである.従来の方法はaの各位置を遍歴し,その後この位置からbと整合するが,この方法の複雑さはO(nm)である.kmpアルゴリズムは,1つのO(m)の前処理により,マッチングの複雑さをO(n+m)に低下させた.
図解の例
コード#コード#
C++

#include
using namespace std;
int KMP(string text, string find)
{
	int j = 0;
	for (int i = 0; i < text.length(); ++i)
	{
		while (j > 0 && text[i] != find[j])
			j =0;
		if (text[i] == find[j])
			j++;
		if (j == find.length())
			return i - j + 1;
	}
	return -1;
}
int main()
{
	string text= "adsgwadsxzdsgwadsgz";
	string find = "dsgwadsgz";
	cout << KMP(text, find);
}

出力結果:(ターゲット文字列が最初に表示された場所)10
Java

public int search(String original, String find) {
	int j = 0;
	for (int i = 0; i < original.length(); i++) {
		while (j > 0 && original.charAt(i) != find.charAt(j))
			j = 0;
		if (original.charAt(i) == find.charAt(j))
			j++;
		if (j == find.length()) 
			return i - j + 1;		
	}
	return -1;
}