串的模式匹配算法（⼀）—朴素的模式匹配算法
串的模式匹配在串的各种操作中是经常⽤到的算法。串的模式匹配也成为⼦串的定位操作，即查找⼦串在主串中出现的位置。本⽂主要讲解串的经典模式匹配算法—Brute-Force。
1 基本思想
串的模式匹配也称为⼦串的定位操作。设有主串S和⼦串T，如果在主串S中找到⼀个与⼦串T相等的⼦串，则返回串T的第⼀个字符在串S 中的位置。其中S称为⽬标串，⼦串T⼜称为模式串。
Brute-Force的基本思想是：从主串S=“S(0) S1 ...S(n-1)”的第pos个字符开始与⼦串T=“T(0) T1 ...T(n-1)”的第⼀个字符⽐较，如果相等则继续⽐较后⼀个字符；否则从主串的下⼀字符开始与⼦串T的第⼀个字符重新开始⽐较，以此类推。如果在主串S中存在与⼦串T相等的连续字符序列，则匹配成功，函数返回⼦串T中第⼀个字符在主串S中的位置；否则，函数返回-1。简单的说，就是对主串的每⼀个字符作为⼦串的开头，与要匹配的字符串进⾏匹配。对主串做⼤循环，每个字符开头做T的长度的⼩循环，直到匹配成功或全部遍历完成为⽌。
假设我们要从主串S=“goodgoogle”中，找到T=“google”这个⼦串的位置。步骤如下：
1. 主串S的第⼀位开始，S与T得前三个字母都匹配成功，但S得第四个字母是d⽽T的是g。第⼀位匹配失
败。如图所⽰，竖直连线表⽰相等，弯折线表⽰不等。
2. 主串S第⼆位开始，主串S⾸字母为o，模式串T的⾸字母为g，匹配失败，如图所⽰：
3.主串S第三位开始，主串S⾸字母为o，模式串T的⾸字母为g，匹配失败，如图所⽰：
4.主串S第四位开始，主串S⾸字母为d，模式串T的⾸字母为g，匹配失败，如图所⽰：
5.主串S第五位开始，S与T，6个字母全匹配，匹配成功，如图所⽰：
2 算法实现
假设串采⽤顺序存储⽅式存储，并假设主串S和模式串T的长度存在S[0]和T[0]中，则Brute-Force匹配算法如下：
1:/* 返回⼦串T在主串S中第pos个字符之后的位置。若不存在，则函数返回值为0 */
2:/* T⾮空,1<=StrLength(S) 。*/
3:int B_FIndex( String S , String T , int pos )
4: {
5:int i = pos ; //i⽤于主串S中当前位置下标，若pos不为1，则从pos位置开始匹配
6:int j = 1 ; //j⽤于⼦串T中当前位置下标
7:while ( i<= S[0] && j <= T[0] ) //若i⼩于S长度且j⼩于T长度时循环
8: {
9:if ( S[i] == T[j] ) //两字母相等时继续
10: {
11: ++i ;
12: ++j ;
13: }
14:el//指针退回重新开始匹配
15: {
16: i = i - j + 2 ; //i退回上次匹配⾸位的下⼀位
17: j = 1 ; //j退回⼦串T的⾸位
18: }
19: }
20:if ( j > T[0] )
21:return i - T[0] ;
22:el
23:return 0 ;
24: }
3 算法分析
Brute-Force匹配算法简单、易于理解，但是执⾏效率不⾼。在此算法中，即使主串与⼦串已有多个字符经过⽐较且相等，但只要有⼀个字符不相等，就需要将主串的⽐较位置退回。
例如，假设主串S=“aaaaaaaaaaaaab”，⼦串T=“aaab”。其中n=14 ，m=4。每次⽐较⼦串的最后⼀个字符与主串中的字符不相等，所以均
需将主串的指针退回，从主串的下⼀个字符开始与⼦串的第⼀个字符重新⽐较。在整个匹配过程中，主串的指针需要退回9次，匹配不成功的⽐较次数10*4，成功匹配的⽐较次数4次，总的⽐较次数为10*4+4=11*4 ，即( n–m+1)*m 。
设主串的长度为n，⼦串的长度为m。Brute-Force匹配算法在最好的情况下，即主串的前m个字符刚好与⼦串相等，时间复杂度为O(m)。在最坏的情况下，Brute-Force匹配算法的时间复杂度为O(n*m)。
