KMP 算法的 C 语言实现

 

# include <stdio.h>
# include <stdlib.h>
# include <string.h>// 打印 KMP 匹配结果.
void ColorPrint(char *T, int *result, int result_size, int m) {int green_size = strlen("\x1b[31m");int reset_size = strlen("\x1b[0m");char *color_string = (char *)malloc((strlen(T) + (green_size + reset_size) * result_size + 1) * sizeof(char));char *temp = (char *)malloc((strlen(T) + (green_size + reset_size) * reset_size + 1) * sizeof(char));strcpy(color_string, T);for (int idx = 0; idx < result_size; idx++) {strcpy(temp, color_string + result[idx] + idx * (green_size + reset_size));color_string[result[idx] + idx * (green_size + reset_size)] = '\0';strcat(color_string, "\x1b[31m");strcat(color_string, temp);strcpy(temp, color_string + result[idx] + m + green_size + idx * (green_size + reset_size));color_string[result[idx] + m + green_size + idx * (green_size + reset_size)] = '\0';strcat(color_string, "\x1b[0m");strcat(color_string, temp);}printf("%s\n", color_string);free(temp);temp = NULL;free(color_string);color_string = NULL;
}// 获得 next 数组.
int *NextArray(char *P, int m) {int *next = (int *)calloc(m, sizeof(int));int idx = 1;int prefix_length = 0;while (idx < m) {if (P[prefix_length] == P[idx]) {next[idx++] = ++prefix_length;} else {if (prefix_length == 0) {idx++;} else {prefix_length = next[prefix_length - 1];}}}return next;
}// KMP 模式匹配算法.
void KMP(char *T, char *P) {int i = 0;int j = 0;int n = strlen(T);int m = strlen(P);int *next = NextArray(P, m);int *result = NULL;int result_size = 0;while (i < n) {if (T[i] == P[j]) {i++; j++;} else {if (j == 0) {i++;} else {j = next[j - 1];}}if (j == m) {result = (int *)realloc(result, (result_size + 1) * sizeof(int));result[result_size++] = i - j;}}ColorPrint(T, result, result_size, m);free(result);result = NULL;free(next);next = NULL;
}int main(int argc, char *argv[], char *env[]) {# ifdef _WIN32system("chcp 65001");KMP("KMP 算法一直是一个比较难以理解的算法。", "算法");# elif __linux__ || __APPLE__KMP("A space Odyssey is not about the Odyssey", "s");# endifreturn 0;
}