programming

KMP算法：高效的字符串模式匹配

算法原理

KMP算法（Knuth-Morris-Pratt算法）是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出。该算法可以在O(n+m)时间内完成匹配，其中n为主串长度，m为模式串长度。

基本思想

  1. 预处理模式串：构建部分匹配表（PMT）或失败函数
  2. 避免回退：利用已匹配的信息，避免主串指针回退
  3. 快速跳转：模式串不匹配时，快速移动到合适位置
  4. 线性时间：保证时间复杂度为O(n+m)

C语言实现

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 构建部分匹配表（失败函数）
void build_failure_function(const char* pattern, int* failure, int m) {
    failure[0] = 0;
    int j = 0;
    
    for (int i = 1; i < m; i++) {
        while (j > 0 && pattern[i] != pattern[j]) {
            j = failure[j - 1];
        }
        
        if (pattern[i] == pattern[j]) {
            j++;
        }
        
        failure[i] = j;
    }
}

// KMP字符串匹配
int kmp_search(const char* text, const char* pattern) {
    int n = strlen(text);
    int m = strlen(pattern);
    
    if (m == 0) return 0;
    if (m > n) return -1;
    
    // 构建失败函数
    int* failure = (int*)malloc(m * sizeof(int));
    build_failure_function(pattern, failure, m);
    
    int j = 0; // 模式串指针
    
    for (int i = 0; i < n; i++) { // 主串指针
        while (j > 0 && text[i] != pattern[j]) {
            j = failure[j - 1];
        }
        
        if (text[i] == pattern[j]) {
            j++;
        }
        
        if (j == m) {
            free(failure);
            return i - m + 1; // 找到匹配，返回位置
        }
    }
    
    free(failure);
    return -1; // 未找到匹配
}

// 查找所有匹配位置
void kmp_search_all(const char* text, const char* pattern) {
    int n = strlen(text);
    int m = strlen(pattern);
    
    if (m == 0 || m > n) return;
    
    int* failure = (int*)malloc(m * sizeof(int));
    build_failure_function(pattern, failure, m);
    
    int j = 0;
    int match_count = 0;
    
    printf("所有匹配位置: ");
    
    for (int i = 0; i < n; i++) {
        while (j > 0 && text[i] != pattern[j]) {
            j = failure[j - 1];
        }
        
        if (text[i] == pattern[j]) {
            j++;
        }
        
        if (j == m) {
            printf("%d ", i - m + 1);
            match_count++;
            j = failure[j - 1]; // 继续查找下一个匹配
        }
    }
    
    if (match_count == 0) {
        printf("无匹配");
    }
    printf("\n总共找到 %d 个匹配\n", match_count);
    
    free(failure);
}

// 打印失败函数（用于调试）
void print_failure_function(const char* pattern) {
    int m = strlen(pattern);
    int* failure = (int*)malloc(m * sizeof(int));
    build_failure_function(pattern, failure, m);
    
    printf("模式串: %s\n", pattern);
    printf("位置:   ");
    for (int i = 0; i < m; i++) {
        printf("%d ", i);
    }
    printf("\n");
    
    printf("字符:   ");
    for (int i = 0; i < m; i++) {
        printf("%c ", pattern[i]);
    }
    printf("\n");
    
    printf("失败值: ");
    for (int i = 0; i < m; i++) {
        printf("%d ", failure[i]);
    }
    printf("\n\n");
    
    free(failure);
}

// KMP算法的优化版本（next数组优化）
void build_next_optimized(const char* pattern, int* next, int m) {
    next[0] = -1;
    int k = -1;
    
    for (int i = 1; i < m; i++) {
        while (k >= 0 && pattern[k + 1] != pattern[i]) {
            k = next[k];
        }
        
        if (pattern[k + 1] == pattern[i]) {
            k++;
        }
        
        // 优化：如果pattern[i] == pattern[next[i]]，
        // 那么next[i] = next[next[i]]
        if (i < m - 1 && pattern[i + 1] == pattern[k + 1]) {
            next[i] = next[k];
        } else {
            next[i] = k;
        }
    }
}

int kmp_search_optimized(const char* text, const char* pattern) {
    int n = strlen(text);
    int m = strlen(pattern);
    
    if (m == 0) return 0;
    if (m > n) return -1;
    
    int* next = (int*)malloc(m * sizeof(int));
    build_next_optimized(pattern, next, m);
    
    int i = 0, j = 0;
    
    while (i < n && j < m) {
        if (j == -1 || text[i] == pattern[j]) {
            i++;
            j++;
        } else {
            j = next[j];
        }
    }
    
    free(next);
    
    if (j == m) {
        return i - j;
    } else {
        return -1;
    }
}

// 演示KMP算法过程
void demonstrate_kmp_process(const char* text, const char* pattern) {
    int n = strlen(text);
    int m = strlen(pattern);
    
    printf("=== KMP算法过程演示 ===\n");
    printf("主串: %s\n", text);
    printf("模式串: %s\n", pattern);
    
    print_failure_function(pattern);
    
    int* failure = (int*)malloc(m * sizeof(int));
    build_failure_function(pattern, failure, m);
    
    int j = 0;
    printf("匹配过程:\n");
    
    for (int i = 0; i < n; i++) {
        while (j > 0 && text[i] != pattern[j]) {
            printf("位置 %d 不匹配，模式串从位置 %d 跳转到位置 %d\n", 
                   i, j, failure[j - 1]);
            j = failure[j - 1];
        }
        
        if (text[i] == pattern[j]) {
            j++;
            printf("位置 %d 匹配，继续比较\n", i);
        } else {
            printf("位置 %d 不匹配\n", i);
        }
        
        if (j == m) {
            printf("在位置 %d 找到完整匹配!\n", i - m + 1);
            break;
        }
    }
    
    free(failure);
}

int main() {
    char text[] = "ABABCABABA";
    char pattern[] = "ABABA";
    
    printf("=== KMP算法测试 ===\n");
    
    // 演示算法过程
    demonstrate_kmp_process(text, pattern);
    
    // 基本搜索
    int pos = kmp_search(text, pattern);
    if (pos != -1) {
        printf("模式串在位置 %d 首次出现\n", pos);
    } else {
        printf("未找到模式串\n");
    }
    
    // 查找所有匹配
    kmp_search_all(text, pattern);
    
    // 测试其他例子
    printf("\n=== 其他测试用例 ===\n");
    
    char text2[] = "AABAACAADAABAABA";
    char pattern2[] = "AABA";
    
    printf("主串: %s\n", text2);
    printf("模式串: %s\n", pattern2);
    kmp_search_all(text2, pattern2);
    
    return 0;
}

复杂度分析

  • 时间复杂度：O(n + m)
  • 空间复杂度：O(m)
  • 预处理时间：O(m)

应用场景

  1. 文本编辑器：查找替换功能
  2. 搜索引擎：网页内容检索
  3. 生物信息学：DNA序列分析
  4. 网络安全：入侵检测系统
  5. 编译器：词法分析

总结

KMP算法是字符串匹配领域的经典算法，其核心思想是利用已匹配的信息避免不必要的回退，从而达到线性时间复杂度。理解KMP算法的关键在于掌握失败函数的构建原理，这不仅是算法实现的基础，也体现了算法设计中”预处理优化”的重要思想。

版权所有，如有侵权请联系我