《数据结构（C语言版）》KMP算法与BF算法
清华大学计算机系列教材 累计发行超400万册
严蔚敏 吴伟民 编著
数据结构（C语言版）
以下是本人对该紫皮书第四章串中4.3节串的模式匹配算法的代码实现，包括KMP算法与BF算法，本人另外include<windows.h>来计算每个算法的运行时间，精确到微秒。
课本上的算法4.5又称BF(Brute Force)暴力算法，时间复杂度O(n*m)，改进后的KMP算法用next数组，再增强KMP算法可用nextval数组，KMP算法比较难理解，这里推荐两个视频https://www.bilibili.com/video/BV1jb411V78H?share_source=copy_web（关于理论部分）
https://www.bilibili.com/video/BV16X4y137qw?share_source=copy_web（关于代码实现，这个视频建议可直接看后面图示法解，通俗易懂next数组的代码实现）
nextval数组感觉会手算就行，原理目前本人也不是特别懂，只是大概明白意思
话不多说上运行结果（注：由于是微秒级别的时间可能有点误差）
（貌似专栏把我缩进吃了，懒得加了，另外建议用visual studio编译，会帮你自动调整缩进）
（预计如果全部更新完会出一个代码合集的压缩包，附上链接以供下载，里面格式为.txt便于大家阅读，希望大家多多支持点个免费的赞）
//BF算法和KMP算法
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <windows.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define MAXSTRLEN 255//用户可以在255以内定义最大串长
typedef int Status;
typedef unsigned char SString[MAXSTRLEN + 1];//0号单元存放串的长度
/*注意这个数据结构和C语言中字符串不同，后者是在字符串末尾设置'\0'，这个是在0号位置存放串长*/
void InputString(SString S);//字符串的输入
int Index(SString S, SString T, int Pos);//返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数值为0
int Index_KMP(SString S, SString T, int Pos);//KMP算法
void get_next(SString T, int next[]);//求模式串T的next函数值并村塾数组next
void get_nextval(SString T, int nextval[]);
double ShowRunTime(SString S, SString T, int pos, int(*Index)(SString S, SString T, int Pos));//显示函数的运行时间
int next[256];
int main()
{
SString MyString;
SString sub;
int pos;
int i;
double runtime;
printf("请输入字符串:");
InputString(MyString);
printf("请输入你想查找的子串:");
InputString(sub);
printf("你想从第几个位置开始查找？");
while (scanf("%d", &pos) != 1)
{
while (getchar() != '\n');
printf("非法输入，请重试\n");
}
runtime = ShowRunTime(MyString, sub, pos, Index);
printf("使用BF算法寻找花费的时间为：%.1f 微秒\n", runtime);
printf("BF算法的时间复杂度为O(n*m)\n");
get_next(MyString, next);//由于一般模式串比较短，get_next执行时间可忽略不计
runtime = ShowRunTime(MyString, sub, pos, Index_KMP);
printf("使用KMP算法寻找花费的时间为：%.1f 微秒\n", runtime);
printf("KMP算法的时间复杂度为O(n+m)\n");
get_nextval(MyString, next);
runtime = ShowRunTime(MyString, sub, pos, Index_KMP);
printf("使用增强版KMP算法寻找花费的时间为：%.1f 微秒\n", runtime);
printf("增强版KMP算法的时间复杂度为O(n+m)\n");
return 0;
}
void InputString(SString S)//字符串的输入
{
int i = 1;
unsigned char c;
while ((c = getchar()) != '\n' && i < 256)
{
S[i] = c;
i++;
}
S[0] = i - 1;
fflush(stdin);//清空输入缓冲区
}
int Index(SString S, SString T, int Pos)//返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数值为0
//T非空，1<=pos<=StrLength(s)
{
int i = Pos;//i指向主串
int j = 1;//j指向子串
while (i <= S[0] && j <= T[0])
{
if (S[i] == T[j])
{
i++;
j++;
}
else
{
i = i - j + 2;//指针后退重新匹配，i-j+1为原位置，再+1即i向后移动一位再匹配
j = 1;
}
}
if (j > T[0])//如果匹配成功，即指向子串的指针成功遍历了一遍子串
{
return i - T[0];
}
else
{
return 0;
}
}
int Index_KMP(SString S, SString T, int Pos)//KMP算法
{
int i = Pos;
int j = 1;
while (i <= S[0] && j <= T[0])
{
if (j == 0 || S[i] == T[j])
{
i++;
j++;
}
else
{
j = next[j];
}
}
if (j > T[0])
{
return i - T[0];
}
else
{
return 0;
}
}
void get_next(SString T, int next[])//求模式串T的next函数值并村塾数组next
{
int i = 1;
next[1] = 0;
int j = 0;
while (i < T[0])
{
if (j == 0 || T[i] == T[j])
{
i++;
j++;
next[i] = j;
}
else
{
j = next[j];
}
}
}
void get_nextval(SString T, int nextval[])
{
int i = 1;
nextval[1] = 0;
int 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];
}
}
}
double ShowRunTime(SString S, SString T, int pos, int(* Index)(SString S, SString T, int Pos))//显示函数的运行时间
{
LARGE_INTEGER BeginTime; //开始时间
LARGE_INTEGER EndTime; //结束时间
double RunTime;
double dqFreq; //计时器频率
LARGE_INTEGER f; //计时器频率
QueryPerformanceFrequency(&f);
dqFreq = (double)f.QuadPart;
QueryPerformanceCounter(&BeginTime);
int i = Index(S, T, pos);
QueryPerformanceCounter(&EndTime);
RunTime = 1000000 * (EndTime.QuadPart - BeginTime.QuadPart) / dqFreq;
if (i)
{
printf("已找到！子串在字符串中的位置为 %d \n", i);
}
else
{
printf("未找到！\n");
}
return RunTime;
}
