C语言实现KMP字符串匹配算法 - 代码详解

#include<stdio.h> #include<string.h>

#define MAXSTRLEN 255 #define OK 1 #define ERROR 0 #define OVERFLOW -2 #define FALSE 0 #define TRUE 1

typedef int Status; typedef unsigned char SString[MAXSTRLEN + 1];

Status StrInit(SString& S);//初始化 Status StrAssign(SString& T, const char* chars);//串赋值 void get_nextval(SString T, int* nextval);//计算模式串T的nextval数组 int Index_KMP(SString S, SString T, int pos);//模式匹配-KMP算法

int main() { SString S, T; int pos; int nextval[MAXSTRLEN + 1]; StrInit(S); StrInit(T); printf("请输入主串 S ："); scanf("%s", S + 1); // 从下标为1的位置开始存储 printf("请输入子串 T : "); scanf("%s", T + 1); // 从下标为1的位置开始存储 get_nextval(T, nextval); pos = Index_KMP(S, T, 1);//pos从1开始 if (pos == ERROR) { printf(" 匹配失败！"); } else { printf("子串T在主串S中的位置：%d\n", pos); } return OK; }

//初始化 Status StrInit(SString& S) { S[0] = 0; return OK; }

//串赋值 Status StrAssign(SString& T, const char* chars) { bool flag; int len = strlen(chars); if (len > MAXSTRLEN) { T[0] = MAXSTRLEN; flag = FALSE; } else { T[0] = len; flag = TRUE; } for (int i = 1; i <= T[0]; i++) T[i] = chars[i - 1]; return flag; }

//计算模式串T的nextval数组 void get_nextval(SString T, int* nextval) { nextval[1] = 0; int i = 1, j = 0; while (i < T[0]) { if (j == 0 || T[i] == T[j]) { ++i; ++j; if (T[i] != T[j]) nextval[i] = j; else nextval[i] = nextval[j]; } else j = nextval[j]; } }

int Index_KMP(SString S, SString T, int pos) { int i = pos, j = 1; int nextval[MAXSTRLEN + 1]; get_nextval(T, nextval); while (i <= S[0] && j <= T[0]) { if (j == 0 || S[i] == T[j]) { ++i; ++j; } else j = nextval[j]; } if (j > T[0]) return i - T[0];//匹配成功 else { return ERROR;//查找失败 }