本篇主要講字符串匹配以及字符串算法中三個(gè)主要算法的一些內(nèi)容，幫助大家理解。

一、基本概念

字符串匹配問(wèn)題

假設(shè)文本是一個(gè)長(zhǎng)度為n的數(shù)組T[1…n]，而模式是一個(gè)長(zhǎng)度為m的數(shù)組P[1…m]，其中m≤n，進(jìn)一步假設(shè)P和T的元素都是來(lái)自一個(gè)有限的字母集∑的字符。數(shù)組T和P通常被稱為字符串。

如果0≤s≤n?m，并且T[s+1…s+m]=P[1…m]，那么稱模式P在文本T中出現(xiàn)過(guò)，且偏移為s。如果P在T中以偏移s出現(xiàn)，那么稱s為有效偏移，否則為無(wú)效偏移。

字符串匹配問(wèn)題就是在T中找到P的所有有效偏移s。

二、字符串匹配算法

（1）BF算法

BF算法，即暴風(fēng)(Brute Force)算法，也叫暴力破解法，是普通的模式匹配算法。

算法思想：將目標(biāo)串S的第一個(gè)字符與模式串T的第一個(gè)字符進(jìn)行匹配，若相等，則繼續(xù)比較S的第二個(gè)字符和 T的第二個(gè)字符；若不相等，則比較S的第二個(gè)字符和T的第一個(gè)字符，依次比較下去，直到得出最后的匹配結(jié)果。

時(shí)間復(fù)雜度：O(n*m)

int BF_match(char *T,char *P){
	int i = 0, j = 0;
	for (; T[i] != '\0' && P[j] != '\0'; i++)
		if (T[i] == P[j])
			j++;
		else
		{
			i -= j;
			j = 0;
		}
	if (P[j] == '\0') return i - j;
	else return -1;
}

（2）BM算法

Boyer-Moore字符串搜索算法是一種非常高效的字符串搜索算法。它由Bob Boyer和J Strother Moore設(shè)計(jì)于1977年。

算法思想：用壞字符表(BS)記錄每個(gè)字符在模式串中最后的位置，用好后綴表(GS)記錄模式串中與后綴匹配的位置，當(dāng)匹配失敗時(shí)，取二者中最大的位移量移動(dòng)，減少字符對(duì)比次數(shù)

時(shí)間復(fù)雜度：O(n/m)~O(n+m)

（3）KMP算法

KMP算法是一種改進(jìn)的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的。

算法思想：用next數(shù)組存儲(chǔ)當(dāng)前字符之前的字符串前、后綴最長(zhǎng)公共元素長(zhǎng)度，匹配失敗時(shí)通過(guò)next數(shù)組偏移

時(shí)間復(fù)雜度：O(n+m)