C语言数据结构中串的模式匹配

什么是字符串的模式匹配？

字符串的模式匹配是指在一个主字符串中查找特定的子串，找到特定的子串后输出其在主字符串中的位置。

例如有一个主串"this is a test string"，要查找的子串为"string"，则字符串的模式匹配应能输出"string"在主串中的位置为17。

如何实现字符串的模式匹配？

字符串的模式匹配可以使用KMP算法、暴力匹配算法等多种算法实现。其中暴力匹配算法比较简单易懂，是初学者的常用选择。

暴力匹配算法

暴力匹配算法，即Brute-Force算法，是最常用的模式匹配算法，它的实现原理是从主串中的每个位置开始，逐个字符地与模式串匹配，当匹配失败时从下一个位置继续进行匹配。

示例代码：

int BruteForce(char* s, char* t) {
    int i = 0, j = 0;
    while (s[i] != '\0' && t[j] != '\0') {
        if (s[i] == t[j]) {
            i++;
            j++;
        }
        else {
            i = i - j + 1;
            j = 0;
        }
    }
    if (t[j] == '\0') {
        return i - j;
    }
    else {
        return -1;
    }
}

其中，参数s为主串，t为待查找的子串。返回子串在主串中的位置，若子串不在主串中，返回-1。

KMP算法

KMP算法是一种快速匹配算法，实现原理是通过预处理模式串，得到匹配失败时下一次匹配所移动的位数，避免暴力匹配算法中多余的比较。KMP算法的时间复杂度为O(m+n)，其中m和n分别为主串和模式串的长度。

代码示例

以下是一个使用暴力匹配算法实现的字符串模式匹配的例子：

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

int BruteForce(char* s, char* t) {
    int i = 0, j = 0;
    while (s[i] != '\0' && t[j] != '\0') {
        if (s[i] == t[j]) {
            i++;
            j++;
        }
        else {
            i = i - j + 1;
            j = 0;
        }
    }
    if (t[j] == '\0') {
        return i - j;
    }
    else {
        return -1;
    }
}

int main() {
    char s[] = "this is a test string";
    char t[] = "string";
    int result = BruteForce(s, t);
    printf("%d", result); // 输出结果为17
}

以下是一个使用KMP算法实现的字符串模式匹配的例子：

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

void GetNext(char *p,int *next) {
    next[0] = -1;   // 从-1开始
    int i = 0;
    int j = -1;
    while (p[i] != '\0') {
        if (j == -1 || p[i] == p[j]) {  
            i++;
            j++;
            next[i] = j;
        }
        else {
            j = next[j];
        }
    }
}

int KMP(char *s,char *p,int *next) {
    int i = 0;
    int j = 0;
    while (s[i] != '\0' && p[j] != '\0') {
        if (j == -1 || s[i] == p[j]) {
            i++;
            j++;
        }
        else {
            j = next[j];
        }
    }
    if (p[j] == '\0') {
        return i - j;
    }
    else {
        return -1;
    }
}

int main() {
    char s[] = "this is a test string";
    char p[] = "string";
    int next[strlen(p)];
    GetNext(p, next);
    int result = KMP(s, p, next);
    printf("%d", result); // 输出结果为17
}

总结

字符串的模式匹配是很常见的需求，对于C语言开发者而言，暴力匹配算法和KMP算法都是实现字符串的模式匹配的有效方法。其中暴力匹配算法比较简单易懂，KMP算法则具有更高的效率。