C语言数据结构之模式匹配字符串定位问题

什么是模式匹配字符串定位？

模式匹配字符串定位即在一个文本串中匹配一个模式串，并且返回模式串在文本串中第一次出现的位置。

例如，对于文本串“this is a test string”，我们想要匹配模式串“test”，我们期望得到的结果是第一次出现的位置为10。

KMP算法

算法思路

KMP算法是一种高效的字符串匹配算法。它的核心是利用已经匹配成功的信息，不断调整模式串的起始位置，从而达到减少匹配次数和提高匹配效率的目的。

具体地，我们用一个next数组来保存模式串每个字符在子串中出现时，如果失配该如何继续匹配的信息。并且我们从前缀和后缀比较的角度来得到每个字符在子串中的next值。

然后在匹配过程中，如果匹配失败了，我们利用next数组来更新模式串的起始位置。具体地，我们让模式串“跳过”已经匹配好的前缀，以达到快速匹配的目的。

代码示例

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

#define maxn 1000010
char p[maxn], t[maxn];
int next[maxn], lenp, lent;

void get_next() {
    int j = 0, k = -1;
    next[0] = -1;
    while (j < lenp) {
        if (k == -1 || p[j] == p[k]) {
            ++j;
            ++k;
            next[j] = k;
        } else {
            k = next[k];
        }
    }
}

int kmp() {
    int i = 0, j = 0;
    while (i < lent && j < lenp) {
        if (j == -1 || t[i] == p[j]) {
            ++i;
            ++j;
        } else {
            j = next[j];
        }
    }
    if (j == lenp) {
        return i - j;
    } else {
        return -1;
    }
}

int main() {
    scanf("%s %s", t, p);
    lenp = strlen(p);
    lent = strlen(t);
    get_next();
    printf("%d", kmp());
    return 0;
}

算法分析

KMP算法的时间复杂度是O(m+n)，其中m和n分别是模式串和文本串的长度。

在实际应用中，通常m远小于n，因此KMP算法可以达到线性级别的时间复杂度，具有较高的效率。

BM算法

算法思路

BM算法是一种查找字符串的优秀算法，它的核心思想是利用规则来跳过尽可能多的匹配。具体地，BM算法分为两个阶段——预处理和匹配。

在预处理阶段，我们需要对模式串p进行预处理，以生成两个跳表，分别是“好后缀”跳表和“坏字符”跳表。

在匹配阶段，我们根据规则决定跳多少步，从而大幅度地减少匹配的次数。具体来说，我们先从右到左地扫描文本串t和模式串p，每当出现不匹配时，我们就利用好后缀和坏字符跳表来计算应该跳过的长度。然后将模式串的起始位置向右移动相应的步数，直到成功匹配模式串或者无法再移动为止。

代码示例

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

#define maxn 1000010
#define max(a, b) ((a)>(b)?(a):(b))

char p[maxn], t[maxn];
int lenp, lent, badchar[128], suffix[maxn], p_mxl[maxn];

void pre_badchar() {
    int l = strlen(p);
    for (int i = 0; i < l; i++) {
        badchar[p[i]] = i;
    }
}

void pre_suffix() {
    int l = strlen(p);
    suffix[l - 1] = l;
    int j = l - 1;
    for (int i = l - 2; i >= 0; i--) {
        if (j < i || suffix[l - j + i - 1] >= j - i) {
            if (j < i) {
                j = i;
            }
            while (j >= 0 && p[j] == p[l - 1 - i + j]) {
                --j;
            }
            suffix[i] = j - i;
        } else {
            suffix[i] = suffix[l - j + i - 1];
        }
    }
}

void pre_p_mxl() {
    int l = strlen(p);
    memset(p_mxl, 0, sizeof(p_mxl));
    for (int i = 0; i < l; i++) {
        int j = suffix[i];
        if (j == i + 1) {
            p_mxl[i] = j;
        } else {
            p_mxl[i] = max(p_mxl[i + 1] - 1, j);
        }
    }
}

int bm() {
    int i = 0, j;
    while (i <= lent - lenp) {
        for (j = lenp - 1; j >= 0 && p[j] == t[i + j]; --j);
        if (j < 0) {
            return i;
        } else {
            i += max(p_mxl[j], j - badchar[t[i + j]]);
        }
    }
    return -1;
}

int main() {
    scanf("%s %s", t, p);
    lenp = strlen(p);
    lent = strlen(t);
    pre_badchar();
    pre_suffix();
    pre_p_mxl();
    printf("%d", bm());
    return 0;
}

算法分析

BM算法是一种高效的字符串匹配算法。一般情况下，BM算法的效率比KMP算法高。

在实际应用中，BM算法的最坏时间复杂度是O(mn)，但在大多数情况下，BM算法能够获得O(m/n)的时间复杂度。