字符串匹配实例讲解

本篇主要讲字符串匹配以及字符串算法中三个主要算法的一些内容，帮助大家理解。

一、基本概念

字符串匹配问题

假设文本是一个长度为n的数组T[1…n]，而模式是一个长度为m的数组P[1…m]，其中m≤n，进一步假设P和T的元素都是来自一个有限的字母集∑的字符。数组T和P通常被称为字符串。

如果0≤s≤n−m，并且T[s+1…s+m]=P[1…m]，那么称模式P在文本T中出现过，且偏移为s。如果P在T中以偏移s出现，那么称s为有效偏移，否则为无效偏移。

字符串匹配问题就是在T中找到P的所有有效偏移s。

二、字符串匹配算法

（1）BF算法

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

算法思想：将目标串S的第一个字符与模式串T的第一个字符进行匹配，若相等，则继续比较S的第二个字符和 T的第二个字符；若不相等，则比较S的第二个字符和T的第一个字符，依次比较下去，直到得出最后的匹配结果。

时间复杂度：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设计于1977年。

算法思想：用坏字符表(BS)记录每个字符在模式串中最后的位置，用好后缀表(GS)记录模式串中与后缀匹配的位置，当匹配失败时，取二者中最大的位移量移动，减少字符对比次数

时间复杂度：O(n/m)~O(n+m)

（3）KMP算法

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的。

算法思想：用next数组存储当前字符之前的字符串前、后缀最长公共元素长度，匹配失败时通过next数组偏移

时间复杂度：O(n+m)