《數(shù)據(jù)結(jié)構(gòu)（C語言版）》KMP算法與BF算法
清華大學(xué)計算機(jī)系列教材? ?累計發(fā)行超400萬冊
嚴(yán)蔚敏 吳偉民 編著
數(shù)據(jù)結(jié)構(gòu)（C語言版）
以下是本人對該紫皮書第四章串中4.3節(jié)串的模式匹配算法的代碼實現(xiàn)，包括KMP算法與BF算法，本人另外include<windows.h>來計算每個算法的運行時間，精確到微秒。
課本上的算法4.5又稱BF(Brute Force)暴力算法，時間復(fù)雜度O(n*m)，改進(jìn)后的KMP算法用next數(shù)組，再增強(qiáng)KMP算法可用nextval數(shù)組，KMP算法比較難理解，這里推薦兩個視頻https://www.bilibili.com/video/BV1jb411V78H?share_source=copy_web（關(guān)于理論部分）
https://www.bilibili.com/video/BV16X4y137qw?share_source=copy_web（關(guān)于代碼實現(xiàn)，這個視頻建議可直接看后面圖示法解，通俗易懂next數(shù)組的代碼實現(xiàn)）
nextval數(shù)組感覺會手算就行，原理目前本人也不是特別懂，只是大概明白意思
話不多說上運行結(jié)果（注：由于是微秒級別的時間可能有點誤差）
（貌似專欄把我縮進(jìn)吃了，懶得加了，另外建議用visual studio編譯，會幫你自動調(diào)整縮進(jìn)）
（預(yù)計如果全部更新完會出一個代碼合集的壓縮包，附上鏈接以供下載，里面格式為.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以內(nèi)定義最大串長
typedef int Status;
typedef unsigned char SString[MAXSTRLEN + 1];//0號單元存放串的長度
/*注意這個數(shù)據(jù)結(jié)構(gòu)和C語言中字符串不同，后者是在字符串末尾設(shè)置'\0'，這個是在0號位置存放串長*/
void InputString(SString S);//字符串的輸入
int Index(SString S, SString T, int Pos);//返回子串T在主串S中第pos個字符之后的位置。若不存在，則函數(shù)值為0
int Index_KMP(SString S, SString T, int Pos);//KMP算法
void get_next(SString T, int next[]);//求模式串T的next函數(shù)值并村塾數(shù)組next
void get_nextval(SString T, int nextval[]);
double ShowRunTime(SString S, SString T, int pos, int(*Index)(SString S, SString T, int Pos));//顯示函數(shù)的運行時間
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算法的時間復(fù)雜度為O(n*m)\n");
get_next(MyString, next);//由于一般模式串比較短，get_next執(zhí)行時間可忽略不計
runtime = ShowRunTime(MyString, sub, pos, Index_KMP);
printf("使用KMP算法尋找花費的時間為：%.1f 微秒\n", runtime);
printf("KMP算法的時間復(fù)雜度為O(n+m)\n");
get_nextval(MyString, next);
runtime = ShowRunTime(MyString, sub, pos, Index_KMP);
printf("使用增強(qiáng)版KMP算法尋找花費的時間為：%.1f 微秒\n", runtime);
printf("增強(qiáng)版KMP算法的時間復(fù)雜度為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);//清空輸入緩沖區(qū)
}
int Index(SString S, SString T, int Pos)//返回子串T在主串S中第pos個字符之后的位置。若不存在，則函數(shù)值為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函數(shù)值并村塾數(shù)組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))//顯示函數(shù)的運行時間
{
LARGE_INTEGER BeginTime; //開始時間
LARGE_INTEGER EndTime; //結(jié)束時間
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;
}
