4-3 串的操作（1）

【算法】串的模式匹配算法

算法目的：确定串中所含子串（模式串）第一次出现的位置

算法应用：搜索引擎、拼写检查、语言翻译

算法实现：

1. BF算法（Brute-Force暴力算法，又称古典的、朴素的、穷举的算法）
2. KMP算法（速度快，难理解）

Brute-Force算法

简称BF算法，采用穷举思想

算法思路：从主串的每一个字符开始依次与模式串的字符进行比较。

将主串的第n个字符和模式串的第一个字符进行比较：

1. 若相等，继续逐个比较后续字符
2. 若不等，从主串的下一字符起，重新与模式串的第一个字符比较
3. 直到主串的一个连续子串字符序列与模式串相等。返回值为主串中与子串匹配的子序列第1个字符的序号，即匹配成功。

代码实现：

int Index_BF(SString S, SString T, int pos) {
	//i和j都从1开始
	int i = pos, j = 1;
	while(i <= S.length && j <= T.length) {
		if(S.chr[i] == T.chr[j]) {
			i++; j++; //主串和子串依次向下匹配下一个字符
		} else {
			i = i - j + 2; //i = (i-j+1)+1
			j = 1;
		}
	}
	//此时j遍历完了，说明子字符串找到
	if(j > T.length) {
		return i - T.length;
	//这是j没有遍历完，说明子字符串未找到
	} else {
		return 0;
	}
}

算法时间复杂度：O(m*n)