简单的模式匹配算法

AI 摘要

|

模式匹配是指在主串中找到与模式串（想要搜索的某个字符串）相同的子串，并返回其所在的位置。这里采用定长顺序存储结构，给出一种不依赖于其他串操作的暴力匹配算法。

int Index(SString S,SString T) {
    int i=1,j=1;
    while(i<=S.length&&j<=T.length) {
        if(S.ch[i]==T.ch[j]){
            ++i;++j;   //继续比较后继字符
        }
        else{
            i=i-j+2;j=1; //指针后退重新开始匹配
        }
    }
    if(j>T.length) return i-T.length;
    else return 0;
}

在上述算法中，分别用计数指针 i 和 j 指示主串 S 和模式串 T 中当前待比较的字符位置。

算法思想是：从主串 S 的第一个字符起，与模式串 T 的第一个字符比较，若相等，则继续逐个比较后续字符；否则从主串的下一个字符起，再重新和模式串 T 的字符比较；以此类推，直至模式串 T 中的每个字符依次和主串 S 中的一个连续的字符序列相等，则称匹配成功，函数值为与模式串 T 中第一个字符相等的字符在主串 S 中的序号，否则称匹配不成功，函数值为零。

在简单模式匹配算法中，设主串和模式串的长度分别为 $n$ 和 $m(n\gg m)$ ，则最多需要进行 $n-m+1$ 趟匹配，每趟最多需要进行 $m$ 次比较，最坏时间复杂度为 $O(nm)$ 。

例如，当模式串为'0000001' 而主串为 '000000000000000000000000000000000000000000001' 时，由于模式串中的前 6 个字符均为 0 ，主串中的前 45 个字符均为 0 ，每趟匹配都是比较到模式串中的最后一个字符时才发现不等，整个匹配过程中指针 i 需要回溯 39 次，总比较次数为 $40\times 7=280$ 次。