文字列マッチング問題------BFアルゴリズムとKMPアルゴリズム

一、BFアルゴリズム:
定義:Brute Forceアルゴリズムは普通のモードマッチングアルゴリズムであり、BFアルゴリズムの思想は目標列Sの最初の文字とモード列Tの最初の文字をマッチングし、等しければSの2番目の文字とTの2番目の文字を比較し続けることである.等しくなければ、Sの2番目の文字とTの1番目の文字を比較し、最後の一致結果が得られるまで順次比較する.
コードは次のとおりです.

int simple(const char *str1, const char *str2)//n*m
{
	assert(NULL != str1 && NULL != str2);

	int sit = 0;
	int i = sit;
	int j = 0;

	while (str1[sit] != '\0' && str1[i] != '\0' && str2[j] != '\0')
	{
		i = sit;
		j = 0;
		while (str1[i] != '\0' && str2[j] != '\0' && str1[i] == str2[j])
		{
			i++;
			j++;
		}                //           ；
		if (str2[j] == '\0')
		{
			return i - j; //       ，       ，                ；
		}
		if (str1[i] == '\0')
		{
			return -1;    //      ，        ；
		} 
		sit++;
	}
	return -1;
}

例:
S: ababcababa
T: ababa
BFアルゴリズムマッチングの手順は以下の通りである.
i=0, j=0
i=1, j=1
i=2,j=2
i=3, j=3
i=4,j=4(失敗)
ababcababa
ababcababa
ababcababa
ababcababa
ababcababa
ababa
ababa
ababa
ababa
ababa
i=1,j=0(失敗)
ababcababa
ababa
i=2,j=0
i=3,j=1
i=4,j=2(失敗)
ababcababa
ababcababa
ababcababa
ababa
ababa
ababa
i=3,j=0(失敗)
ababcababa
ababa
i=4,j=0(失敗)
ababcababa
ababa
i=5,j=0
i=6,j=1
i=7,j=2
i=8,j=3
i=9,j=4(成功)
ababcababa
ababcababa
ababcababa
ababcababa
ababcababa
ababa
ababa
ababa
ababa
ababa
 
二、KMPアルゴリズム:
定義:
KMPアルゴリズムは改良された文字列マッチングアルゴリズムであり、KMPアルゴリズムの鍵はマッチングに失敗した情報を利用して、パターン列と主列のマッチング回数をできるだけ減らして、迅速なマッチングの目的を達成することである.具体的な実装はnext()関数を実現し,関数自体にモード列の局所整合情報が含まれている.時間複雑度O(m+n).
主列T:a b a a c a a b a c a b a b a b a b b
パターン列S:a b a c a b
暴力的な文字列マッチングの過程で、T[0]とW[0]をマッチングし、等しい場合は次の文字をマッチングし、等しくない場合になるまで、前のマッチング情報を簡単に破棄し、T[1]とW[0]をマッチングし、メイン列が終わるまでループしたり、マッチングが発生したりします.このような単純な前のマッチング情報の破棄は,大きな浪費とマッチング効率の低下をもたらした.しかし,KMPアルゴリズムでは,各パターン列についてパターン列の内部整合情報を事前に計算し,整合失敗時にパターン列を最大に移動させて整合回数を減らす.
たとえば,単純なマッチングに失敗した後,パターン列をできるだけ右にシフトして主列とマッチングしたい.右シフトの距離はKMPアルゴリズムで計算される:一致したモード列のサブ列の中で、最も長い同じ接頭辞と接尾辞を見つけて、それからそれらを重ねて移動します.
1回目のマッチングで
 T: a b a c a a b a c a b a c a b a a b b
W: a b a c a b
T[5]とW[5]では不整合が発生し、T[0]~T[4]は整合しているが、現在T[0]~T[4]は前述の一致したパターン列のサブ列であり、現在移動して最も長い同じ接頭辞と接尾辞を探し出して重複させる.
 T: a b a c a a b a c a b a c a b a a b b
W: a b a c a b
その後、前回のマッチングに失敗した場所からマッチングを行うことで、マッチング回数が減少し、効率が向上します.
実装コードは次のとおりです.

void getNext(const char *str, int *next)
{
	assert(NULL != str && NULL != next);
	next[0] = -1;
	int i = -1;
	int j = 0;

	while (j <= strlen(str))
	{
		if (i == -1 || str[i] == str[j])
		{
			i++;
			j++;
			next[j] = i;
		}
		else
		{
			i = next[i];
		}
	}
}
 


int KMP(const char *str1, const char *str2)
{
	assert(NULL != str1 && NULL != str2);

	int *next = (int*)malloc(sizeof(int)*strlen(str2));
	assert(NULL != next);
	getNext(str2, next);
	int i = 0;
	int j = 0;
	while (str1[i] != '\0' && j < strlen(str2))
	{
		if (str1[i] == str2[j])
		{
			i++;
			j++;
		}
		else
		{
			j = next[j];
		}
	}
	if (j == strlen(str2))
	{
		return i - j;
	}
	return -1;
}

KMPアルゴリズムはさらに最適化できる.
例えば、与えられたP文字列は「abcdaabcab」であり、KMPアルゴリズムにより、「特徴ベクトル」は以下の表に示すように得られるべきである.
下付きi
0
1
2
3
4
5
6
7
8
9
p(i)
a
b
c
d
a
a
b
c
a
b
next[i]
-1
0
0
0
0
1
1
2
3
1
ただし、p(i)==p(k)が見つかった場合は、対応するnext[i]の値をnext[k]の値に変更する必要があります.最適化すると、次の表が得られます.
下付きi
0
1
2
3
4
5
6
7
8
9
p(i)
a
b
c
d
a
a
b
c
a
b
next[i]
-1
0
0
0
0
1
1
2
3
1
最適化next[i]
-1
0
0
0
-1
1
0
0
3
0