文字列一致クラシック

最近データ構造を磨いて、文字列マッチングアルゴリズムKMP、BM、KPなどを見て、面接でできるべき知識点だと感じて、先に記録して、便利になってから復習して見ます:
      1.KMPアルゴリズム
KMPアルゴリズムは、暴力的なアルゴリズムの上でいくつかの改良を行い、現在の比較に失敗した接頭辞を繰り返さない.すなわち、マッチング列自体の情報を利用して、クエリテーブルnextを構築し、このテーブルは、マッチングに失敗した場合に、マッチング列をどのように移動するかを指導することができる.比較を繰り返す無駄な操作は省略できます.
1.1 nextテーブル構造
nextテーブルの構造は本質的に文字列のマッチングであるため、全体のフレームワークはKMPと類似している.
 

int* buildnext(const char* p)
{
	size_t m = strlen(p), j = 0;
	int* N = new int[m];
	int t = N[0] = -1;
	while (j < m - 1)
	{
		if (t < 0 || p[j] == p[t])
		{
			j++; t++;
			N[j] = t;
		}
		else
			t = N[t]; // t      ，        
	}
	return N;
}

1.2.KMPアルゴリズム構築:
KMPの核心は主に1.1の中のクエリー表であり、二次マッチングが失敗した場合、マッチング列を適当な位置にジャンプさせ、新しくマッチングを開始することができる.

int KMPMatch(const char* p, const char* T)
{
	int* next = buildnext(p);
	int n = strlen(T), i = 0;
	int m = strlen(p), j = 0;
	while (j < m && i < n)
		if (j < 0 || p[j] == T[i])
		{
			i++; j++;
		}
		else
			j = next[j];
	delete[] next;
	return i - j;
}

1.3 nextテーブルの改善

int* buildnext(const char* p)
{
	size_t m = strlen(p), j = 0;
	int* N = new int[m];
	int t = N[0] = -1;
	while (j < m - 1)
	{
		if (t < 0 || p[j] == p[t])
		{
			j++; t++;
			N[j] = (p[j]!=p[t] ? t : N[t]);
		}
		else
			t = N[t]; // t      ，        
	}
	return N;
}

 
2.BMアルゴリズム
さらに最適化され、悪い文字と良い接尾辞のポリシーを採用します.悪い文字は文字マッチングの「教訓」を利用して最適化され、良い接尾辞は文字マッチングの先行知識「経験」を利用して最適化されます.両者を組み合わせてもよいし、別々に最適化を実施してもよい.次に,悪字BCと接尾辞GS最適化戦略をそれぞれ紹介する.
2.1悪字表構造
悪い文字とは、マッチング列pが右から左へTにマッチングしたときに、不一致Tの中の文字が現れることである.この不一致の教訓に基づいて、pが一致するには、次の一致を行うには、左側にこの悪い文字を見つけなければなりません.

int* buildBC(const char* p)
{
	int* bc = new int[256];  //      
	for (size_t j = 0; j < 256; j++) bc[j] = -1; //    ，         p 
	for (size_t m = strlen(p), j = 0; j < m; j++)
		bc[p[j]] = j; //        p    Rank
	return bc;
}

2.2悪文字に基づくマッチングアルゴリズム
悪い文字の次のジャンプが確定した以上、次の一致する相対位置関係を出すことができます.

int BMMatch(const char* p, const char* T)
{
	int* bc = buildBC(p);
	size_t i = 0;  //T    
	while (strlen(T) >= i + strlen(p)) { // T       
		int j = strlen(p) - 1;
		while (p[j] == T[i + j]) //p T       
			if (0 > --j) break;
		if (0 > j)
			break;
		else
			i += j - bc[T[i + j]]; //  bc    p       ，       
	}
	delete[] bc;
	return i;
}