KMP实现和笔记

#include <stdio.h>
#include <string.h>
#define MAXN 100000
#define MAXM 100000

char str[MAXM];
char pattern[MAXM];
int m, n;

int pi[MAXM];

// 计算前缀函数
void compute_pi() {
    int k = 0;
    pi[0] = 0;
    pi[1] = 0;
    for (int i = 2; i <= m; ++i) {
        // 特别注意i-1
        while (k > 0 && pattern[i-1] != pattern[k]) {
            k = pi[k];
        }
        if (pattern[i-1] == pattern[k]) {
            k++;
        }
        pi[i] = k;
    }
}

void print_match(int index) {
    printf("%s\n", str);
    for (int i = 0; i < index; ++i) {
        if (index - i < m) {
            putchar('-');
        } else {
            putchar(' ');
        }
    }
    putchar('^');
    putchar('\n');
}

void print_array(int *arr, int k) {
    for (int i = 0; i < k; ++i) {
        printf("%d ", pi[i]);
    }
    putchar('\n');
}

// 匹配
void find_all_matches() {
    int j = 0;
    // i始终无需减少
    for (int i = 0; i < n; ++i) {
        // 失配，则j回退到pi[j]
        // j最多回退到0
        while (j > 0 && str[i] != pattern[j]) {
            j = pi[j];
        }
        // 匹配，则j和i都+1
        if (str[i] == pattern[j]) {
            j++;
        }
        if (j == m) {
            printf("match @ %d\n", i);
            print_match(i);
            j = pi[m]; // 匹配完成，假装失配
        }
    }
}

int main() {
    printf("pattern\n");
    scanf(" %s", pattern);
    printf("str\n");
    scanf(" %s", str);
    m = strlen(pattern);
    n = strlen(str);
    compute_pi();
    print_array(pi, m+1);
    find_all_matches();
    return 0;
}