串的模式匹配算法（一）—朴素的模式匹配算法

    串的模式匹配在串的各种操作中是经常用到的算法。串的模式匹配也成为子串的定位操作，即查找子串在主串中出现的位置。本文主要讲解串的经典模式匹配算法—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匹配算法如下：

/* 返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数返回值为0 */
/* T非空,1<=StrLength(S) 。*/
int B_FIndex( String S , String T , int pos )
{
    int i = pos ;       //i用于主串S中当前位置下标，若pos不为1，则从pos位置开始匹配
    int j = 1 ;         //j用于子串T中当前位置下标
    while ( i<= S[0] && j <= T[0] )  //若i小于S长度且j小于T长度时循环
    {
        if ( S[i] == T[j] )           //两字母相等时继续
        {
            ++i ;
            ++j ;
        }
        else                        //指针退回重新开始匹配
        {
            i = i - j + 2 ;         //i退回上次匹配首位的下一位
            j = 1 ;                 //j退回子串T的首位
        }
    }
    if ( j > T[0] )
        return i - T[0] ;
    else
        return 0 ;
}

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)。