字元串比對的BF算法與KMP算法

1.BF算法

//T為文本串如"Now is the time"，P為模式串如"time"，時間複雜度O(m*n)，其中m與n為P和T的長度
int bf_match(string P, string T)
{
	int sizeP = P.size();
	int sizeT = T.size();
	int i = 0, j = 0;
	for (; i < sizeP - sizeT + 1; i++)
	{
		for (; j < sizeT; j++)
		{
			if (T[j] != P[i + j])
				break;
		}
		if (j >= sizeT)
			break;
	}
	return (i < sizeP - sizeT + 1) ? (i) : (-1);  //這裡的i在成功時傳回的是成功的位置，失敗則是-1
}
           

2.KMP算法

• （1）KMP算法的核心，是一個被稱為部分比對表(Partial Match Table)的數組，PMT中的值是字元串的字首集合與字尾集合的交集中最長元素的長度。例如，對于”aba”，它的字首集合為{”a”, ”ab”}，字尾 集合為{”ba”, ”a”}。兩個集合的交集為{”a”}，那麼長度最長的元素就是字元串”a”了，長 度為1，是以對于”aba”而言，它在PMT表中對應的值就是1。再比如，對于字元串”ababa”，它的字首集合為{”a”, ”ab”, ”aba”, ”abab”}，它的字尾集合為{”baba”, ”aba”, ”ba”, ”a”}， 兩個集合的交集為{”a”, ”aba”}，其中最長的元素為”aba”，長度為3。
• （2）我們看到如果是在 j 位 失配，那麼影響 j 指針回溯的位置的其實是第 j −1 位的 PMT 值，是以為了程式設計的友善， 我們不直接使用PMT數組，而是将PMT數組向後偏移一位。我們把新得到的這個數組稱為next數組。
• （3）現在，我們再看一下如何程式設計快速求得next數組。（next數組隻與模式串字元串自身有關，與文本字元串無關，是以可以單獨建構）其實，求next數組的過程完全可以看成模式字元串自比對的過程，一旦字元串比對成功，那麼目前的next值就是比對成功的字元串的長度。具體來說，就是從模式字元串的第一位(注意，不包括第0位，第0位必為-1，模式串的第一個字元就是第一位)開始對自身進行最長前字尾集的運算。 在任一位置，能比對的最長長度就是目前位置的next值。（next數組的next[0] = -1，next[1] = 0，雷打不動，從next[2]開始真正計算，此時可以了解為模式串的j為0，而文本串的i為1，其中i與j為0時均為首）
• （4）總結KMP算法思想，首先根據模式串自身特性，建立Next數組，其中存儲在第多少位失配時，模式串自身回到多少位的資訊。然後在主算法中，進行文本串i的按位比對，每當出現失配時，i位置不變，而j根據Next數組回到一個相對較優的位置繼續判斷。Next[0] = -1實作的基礎為j=-1.其核心在于使每次j = 0時都配對不上而回到Next[0]時能順利進行而不是陷入死循環

int *buildNext(string P)
{
	int sizeP = P.size();
	int *Next = new int[sizeP + 1]; //注意n+1，使代碼能夠存到Next[sizeP]
	int i = 0; int j = -1;   //雙指針，i代表文本串指針，j代表模式串指針（這裡的文本串和模式串都是P自身）
	Next[0] = -1;
	while (i < sizeP)
	{
		if (j == -1 || P[i] == P[j])
		{
			i++;
			j++;
			//Next[i] = j;
			Next[i] = ((P[i] != P[j]) ? (j) : (Next[j]));   //優化的Next建表判斷，吸取前面的當P[i] == P[j]時的經驗
		}
		else
			j = Next[j];    //Next用于存儲當失配時，模式串自身将回到的位置，是以這裡可以在失配時調用自己回到對應的位置j
	}
	return Next;
}

int KMP_match(string P, string T)
{
	if (T.empty())
		return 0;

	int sizeP = P.size();
	int sizeT = T.size();

	if (sizeP > sizeT)
		return -1;

	int *next = buildNext(P);
	int i = 0, j = 0;    //i為文本串的指針，而j為模式串的指針
	while (i < sizeT && j < sizeP)
	{
		if (j == -1 || T[i] == P[j])   //注意next[0] = -1，是以j可能被移到-1位
		{
			i++;
			j++;
		}
		else
			j = next[j];   //模式串右移，注意文本串不會回退，next表用于存儲當出現失配時j應該回退的地方
	}
	delete[] next;
	return (j == sizeP) ? (i - j) : (-1);;
}