文章目錄

1.暴力匹配(BF算法)

暴力匹配，也稱為簡單匹配算法，采用窮舉的思想，從主串的第一個字符開始和模式串中第一個字符比較。

若相等，則依次比較后續字符，如果不相等，模式串回溯為第一個字符，從主串的第二個字符開始重新和模式串比較，實現如下：

#include
int BF(char *s,char *t)//s為主串，t為模式串 
{
	int i = 0,j = 0;
	while(s[i]!='\0'&&t[j]!='\0')//兩個串都沒有掃描完時循環 
	{
		if(s[i]==t[j])//當前兩個字符相同 
		{
			i++;j++;//比較后續字符 
		}
		else//當前兩個字符不同 
		{
			i=i-j+1;//掃描主串的i回退 
			j=0;//模式串回溯為0，從頭匹配 
		}
	}
	if(t[j]=='\0')//如果j越界，表示模式串遍歷完，t是s的字串 
		return i-j;//返回目標串中子串的起始位置 
	else
		return 0;
}
int main()
{
	char s[5]={'a','c','a','b','a'};
	char t[2]={'a','b'};
	printf("%d",BF(s,t));
}

算法時間復雜度分析：

1.最好的情況，即不需要回溯，一次匹配成功，復雜度為O(m)

2.最壞的情況，需要多次回溯時，復雜度為O(n×m)

3.算法平均時間復雜度為O(n×m)

2.KMP算法

該算法相比較暴力算法，有很大的改進，消除了主串指針的回溯，如下圖進行字符串s和t的匹配：

用 i 和 j 來掃描字符串s和t，此時匹配失敗處為 i = 3,j = 3,雖然本次匹配失敗，但仍然取得了部分匹配的信息，s1s2 與 t1t2 相同。

而且這時還發現字符串t中前兩個字符和中間兩個字符相等，即t1t2 = t0t1,所以s1s2 = t0t1,如下圖所示。

而原本第二趟匹配應該從i = 1，j=0開始匹配，現在既然有s1s2 = t0t1,那么第二趟匹配的 j = 0,j = 1 就可以直接跳過，直接從 i =3, j = 2開始第二趟匹配。

從上匹配過程可以發現，在匹配失敗時，我們利用從模式串t中提取的有用信息，消除了主串指針的回溯，這種信息是對于t中的每一個字符 t[j],存在一個整數k使得字符串t開頭的k個字符和 t[j] 的前面k個字符相同，如果這樣的k存在多個，取最大的那個。

如上述字符串"aaab"，當t[3]='b’時，b前面的一個字符"a"和開頭的一個字符"a"相同，k=1，b前面的兩個字符"aa"和開頭的兩個字符"aa"相同,即k=2,所以取最大值k=2。

對于模式串t的每個字符，都對應一個k，我們用一個next數組來保存，由模式串t求next數組的算法如下：

void GetNext(char *t,int next[])//求出next數組，消除主串指針回溯 
{
	int j=0,k=-1;//j掃描模式串t，k記錄t[j]之前與t開頭相同的字符個數 
	next[0]=-1;//開頭字符的k值為-1
	while(t[j]!='\0')
	{
		if(k==-1||t[j]==t[k])//掃描到相同字符時，k++
		{
			j++;k++;
			next[j]=k;
		}
		else
		k=next[k];//k回退 
	}
}

取得加速匹配的信息后，當出現匹配失敗時，令 j = next[j] ,消除主串指針回溯，KMP算法如下：

#define MaxSize 50
int KMP(char *s,char *t)
{
	int next[MaxSize],length;
	int i=0,j=0;
	GetNext(t,next);
	length=strlen(t);
	while(s[i]!='\0'&&j<length)
	{
		if(j==-1||s[i]==t[j])//j=-1或者當前兩個字符相同  
		{
			i++;
			j++;
		}
		else
		{
			j=next[j];//回退到j=next[j]，即模式串右滑 
		}
	}
	if(t[j]=='\0')
		return i-j;
	else
		return 0;
}

KMP算法時間復雜度分析：設主串s長度為n，模式串t長度為m，在KMP算法中求next數組的時間復雜度為O(m)，在后面的匹配中因主串s的下標不回溯，比較次數可記為n，所以KMP算法平均時間復雜度為O(n+m)。