介绍

模式匹配是数据结构中字符串的一种基本运算，给定一个子串，要求在某个字符串中找出与该子串相同的所有子串，这就是模式匹配。

假设P是给定的子串，T是待查找的字符串，要求从T中找出与P相同的所有子串，这个问题成为模式匹配问题。P称为模式，T称为目标。如果T中存在一个或多个模式为P的子串，就给出该子串在T中的位置，称为匹配成功；否则匹配失败。

简单的模式匹配算法 — 蛮力算法 (BF算法)
蛮力算法(Brute-Force)，简称BF算法。

算法思想

BF算法的算法思想是：

从目标串T的的第一个字符起与模式串P的第一个字符比较。

若相等，则继续对字符进行后续的比较；否则目标串从第二个字符起与模式串的第一个字符重新比较。

直至模式串中的每个字符依次和目标串中的一个连续的字符序列相等为止，此时称为匹配成功，否则匹配失败。

通过下图示例，可一目了然：

算法性能

假设模式串的长度是m，目标串的长度是n。

最坏的情况是每遍比较都在最后出现不等，即没变最多比较m次，最多比较n-m+1遍。

总的比较次数最多为m(n-m+1)，因此BF算法的时间复杂度为O(m*n)。

BF算法中存在回溯，这影响到效率，因而在实际应用中很少采用。

实现代码

#include <stdio.h>
#include <string.h>

int Index(char *txt, char* str) {
    int str_len = strlen(str);//计算字符串长度
    int txt_len = strlen(txt);
    for (int i = 0; i < txt_len; i++) {
        int flag = 0;
        for (int j = 0; j < str_len; j++) {
            if (txt[i + j - 1] != str[j]) {
                flag = 1;//发现不匹配
                break;
            }
        }
        if (flag == 0) {//如果找到了就结束
            return i;
        }
    }
    return -1;
}

int main() {
    char txt[1005];//文本串
    char str[1005];//模式串
    scanf("%s", txt);
    scanf("%s", str);
    int ans = Index(txt, str);
    if (ans == -1) {
        printf("not find!\n");
    }
    else {
        printf("find! index is %d\n", ans);
    }
    return 0;
}

KMP算法

Knuth-Morris-Pratt算法（简称KMP），是由D.E.Knuth、J.H.Morris和V.R.Pratt共同提出的一个改进算法，...

课后习题

【2019年真题】设主串T=“abaabaabcabaabc”，模式串S=“abaabc”，采用KMP算法进行模式匹配，到匹配成功时为止，在匹配过程中进行的单个字符间的比较次数是
A. 9               B. 10                   C. 12                   D. 15

参考答案：B

【2015年真题】已知字符串 S 为“abaabaabacacaabaabcc”，模式串 t 为“abaabc”。采用 KMP 算法进行匹配，第一次出现“失配”(s[i]≠t[j]) 时，i=j=5，则下次开始匹配时，i 和j 的值分别是（）。
A．i=1,j=0    B．i=5,j=0    C．i=5,j=2    D．i=6,j=2 

参考答案：C