字符串匹配算符

朴素模式匹配算法

朴素模式匹配算法是字符串模式匹配算法中最简单的蛮力解法，有称为BF算法

int PatternMatchBF(char* s, char* t)
{
    int p;
    int n = strlen(s);
    int m = strlen(t);
    for (p = 0; p <= n - m; p++) {
        int i;
        for (i = 0; i < m; i++) {
            if (s[p + i] != t[i]) {
                break;                
            }
        }
        if (i == m) {
            break;
        }
    }
    if (p > n - m) {
        p = 0;
    }
    return p;
}

KMP算法

查找过程

以W="ABCDABD"，S="ABC ABCDAB ABCDABCDABDE"为例说明查找过程。查找过程同时使用两个循环变量m和i：

• m代表主文字符串S内匹配字符串W的当前查找位置，
• i代表匹配字符串W当前做比较的字符位置。

             1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W: ABCDABD
i: 0123456

从W与S的开头比较起。比对到S[3](=’ ‘)时，发现W3与之不符。接著并不是从S[1]比较下去。已经知道S[1]~S[3]不与W[0]相合。因此，略过这些字元，令m = 4以及i = 0。

             1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:     ABCDABD
i:     0123456

如上所示，检核了"ABCDAB"这个字串。然而，下一字符便不相合。可以注意到，“AB"在"ABCDAB"的头尾处均有出现。这意味著尾端的"AB"可以作为下次比较的起始点。因此，令m = 8, i = 2，继续比较。

             1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:         ABCDABD
i:         0123456

于m = 10的地方，又出现不相符的情况。类似地，令m = 11, i = 0继续比较：

             1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:            ABCDABD
i:            0123456

这时，S17不与W[6]相同，但是已匹配部分"ABCDAB"亦为首尾均有"AB”，采取一贯的作法，令m = 15和i = 2，继续搜寻。

             1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:                ABCDABD
i:                0123456

找到完全匹配的字串了，其起始位置于S[15]的地方。

1. 核心思想 当出现失配情况时，如何将模式串向右移动正确的位数。
2. 计算模式串向右移动的位数 KMP算法中模式串向右移动的位数由已匹配部分字符串的最长公共前后缀长度确定。

• (1) 字符串特征向量 首先引入字符串特征向量概念。长度为m的字符串t的特征向量是一个m维向量，通常记作next，且用数组形式进行存储，所以特征向量也可以非正式地称为next数组。

  以"ABCDABD"为例

KMP主要流程：在匹配到模式串t的第i位(i从1开始)发生失配时，将模式串向右移动i - 1 - next[i-1](理解：因为第i位字符不匹配，所以至少移动i-1位，由于有公共字串，需要减去公共字串的长度)，从模式串t的第next[i-1]+1位重新开始分配，直到达字符串末尾。

• (2)字符串特征向量的计算方法

int* GetNext(char* t, int* next)
{
    int m = strlen(t);
    next[0] = -1;
    for (int i = 1; i < m; i++) {
        int j = next[i - 1];
        while (j >= 0 && t[i] != t[j + 1]) {
            j = next[j];
        }
        if (t[i] == t[j + 1]) {
            next[i] = j + 1;
        } else {
            next[i] = -1;
        }
    }
    return next;
}

• (3)字符串匹配的KMP算法

int PatternMatchKMP(char* s, char* t)
{
    int n = strlen(s);
    int m = strlen(t);
    int p = -1;
    if (n >= m) {
        int* next = (int*)malloc(m * sizeof(int));
        GetNext(t, next);
        int i = 0;
        int j = 0;
        while (j < n && i < m) {
            if (s[i] == t[j]) {
                i++;
                j++;
            } else if (i > 0) {
                i = next[i - 1] + 1;
            } else {
                j = j + 1;
            }
        }
        if (i == m) {
            p = j - m;
        }
    }
    return p;
}