发表于 | | 次阅读

@TOC

字符串模式匹配

简单的字符串模式匹配算法

串的模式匹配是求第一个字符串在第二个字符串中的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int Index(String str, String t) {
    //  求字符串t在str中的位置。
    //  str[0]和t[0]存储的是字符串的长度；
    int i = 1, j = 1;
    while(i <= str[0] && j <= t[0]) {
        if(str[i] == t[j]) {
            i++;
            j++;
        } else {
            i = i - j + 2;
            j = 1;
        }
    }
    if (j > t[0])
        return i - t[0];
    return 0;
}

简单模式匹配算法的时间复杂度为O(m*n)，m和n分别为主串和模式串的长度。

改进的模式匹配算法——KMP算法

KMP算法可以在O(m+n)的时间数量级上完成串的模式匹配操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
void get_next(char T[], int next[]) {
    int i = 1;
    next[1] = 0;   //  next[0]不使用
    int j = 0;
    while(i <= T[0]) {
        if (j == 0 || T[i] == T[j]) {
            ++i;
            ++j;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
}

int KMP(char S[], char T[], int next[], int pos) {
    //  求模式串T在主串S中第pos个字符之后的位置的KMP算法
    i = pos;
    j = 1;
    while(i <= S[0] && j <= T[0]) {
        if(j == 0 || S[i] == T[j]) {
            ++i;
            ++j;
        } else {
            j = next[j];
        }
    }

    if(j > T[0])
        return i - T[0];
    return 0;
}