编辑代码

#include <stdio.h>  
#include <string.h>  
  
// 函数用于计算next数组  
void computeNext(char *pattern, int *next, int m) {  
    int j = 0;  
    next[0] = -1; // 第一个字符的next值为-1  
    int k = -1;  
    while (j < m - 1) {  
        if (k == -1 || pattern[j] == pattern[k]) {  
            j++;  
            k++;  
            next[j] = k;  
        } else {  
            k = next[k];  
        }  
    }  
}  
  
// KMP算法的主函数  
void KMPSearch(char *text, char *pattern) {  
    int n = strlen(text);  
    int m = strlen(pattern);  
    int *next = (int *)malloc(m * sizeof(int));  
      
    computeNext(pattern, next, m);  
  
    int i = 0; // text的索引  
    int j = 0; // pattern的索引  
    while (i < n) {  
        if (j == -1 || text[i] == pattern[j]) {  
            i++;  
            j++;  
        }  
        if (j == m) {  
            printf("Pattern found at index: %d\n", i - j);  
            j = next[j - 1]; // 继续查找下一个匹配  
        } else if (i < n && text[i] != pattern[j]) {  
            j = next[j]; // 文本和模式串当前字符不匹配，模式串回溯  
        }  
    }  
    free(next);  
}  
  
int main() {  
    char text[] = "ABABDABACDABABCABAB";  
    char pattern[] = "ABABCABAB";  
    KMPSearch(text, pattern);  
    return 0;  
}