数据结构

课程设计报告

设计题目：模式匹配中的KMP算法的实现

专业：计算机科技

院系：计算机学院

姓名：xxxxxxxx

学号：xxxxxxx

时间：2013年9月22日

目 录

1 需求分析 3

1.1 问题描述 3

1.2 基本要求 3

2 概要设计 3

3 详细设计 5

3.1 为主串和模式串赋值 5

3.2 利用Output（）函数输出串。 -5

3.3 求各串的长度 6

3.4 求模式串的模式值next[]函数 6

3.5 模式匹配KMP算法的实现： 7

4 测试与分析 7

5 总结 9

6 附录：源程序清单 9

参考文献 13

1 需求分析

1.1 问题描述

KMP算法是对一般模式匹配算法的改进，由D.E.Knuth与V.R.Pratt和J.H.Morris 同时发现的因此人们称它为克努特-莫里斯-莫拉特操作（简称为KMP算法）。

对于一般的模式匹配算法：分别利用两个指针i和j指示主串S和T中的当前正待比较的字符位置。算法的基本思想是：从主串的S的第POS个字符开始起和模式的第一个字符比较之，如相等，则继续逐个比较后续字符；否则从主串的下一个字符起再重新和模式的字符比较之。以此类推，直到模式T中的每个字符依次和主串S中的一个连续字符序列相等，则称匹配成功，则函数值为和模式T中的第一个字符相等的字符在主串S中的序号，否则称匹配不成功，函数值为0.而对于模式匹配的KMP算法可以在O(n+m)的时间数量级上完成串的模式匹配操作。其改进过程在于：每当一趟匹配过程出现字符比较不相等时，不需回溯i指针，而是利用已经得到的部分匹配的结果将模式串向右滑动一段尽可能远的距离后，继续进行比较。滑动的这一段距离我们将会用到函数Next[],

KMP算法的最大特点是指示主串的指针不须回溯，整个匹配过程中，对主串仅需从头到尾扫描一遍，这对处理从外设输入的庞大文件很有效，可以边度入边匹配，而无需回头重读。

开发工具：C语言

1.2 基本要求

用C编写一个程序实现模式匹配的KMP算法。要求对于任何输入串A，实现算法求next 函数值；利用next函数值，实现串A在串B中的定位；若未搜索到，就返回0。 首先要从键盘输入主串B和模式串A，并采用用链式存储，再根据Next( )函数求模式串的Next值，利用KMP 算法进行匹配，再用输出函数输出结果！

2 概要设计

对该kmp 算法，定义的抽象数据类型如下：

ADT String{

数据对象：D={ai|ai∈CharacterSet,i=1,2,3,…,n,n≥0}

数据关系：R1={i-1,ai>|ai-1,ai∈D,i=2,…,n}

基本操作：StrAssign(&T,chars)

初始条件：chars是字符串常量。

操作结果：生成一个其值等于chars的串T。

StrCopy（S）

初始条件：串S存在。

操作结果：若S为空串，则返回TRUE，否则返回FALSE。

StrLength(S)

初始条件：串S存在。

操作结果：返回S元素的个数，成为串的长度。

Index(S,T,pos)

初始条件：串S和T存在，T是非空串，1≤pos≤StrLength(S).

操作结果：若主串S中存在和串T相同的子串，则返回他在主串S中的第pos个字符之后第一次出现的位置；否则函数值为0。

DestoryString(&S)

初始条件：串S存在。

操作结果：串S被销毁。

}ADT String

该算法是对串进行操作，对串的存储结构用线性表的链式存储结构表示：

typedef struct LString{

char data；

struct LString *next；

}LString；

该算法分为三个模块：第一模块[Input( )函数]（利用该函数输入主串和模式串）；第二模块[Output( )函数利用该函数输出串）。第三模块[Length（）]（利用该函数求各串的长度）；第四模块[Get_next( )函数]（利用该函数求出模式串的next函数值）；第五模块[Index_KMP（）函数]（利用该函数进行主串和模式串之间的匹配）；各个模块之间的调用关系如下图所示：图2.1是对整个函数的流程图。

整个函数的流程图

3 详细设计：

3.1 为主串和模式串赋值

利用Input（）函数输入主串和模式串Input（）

函数伪代码：

LString *Input(){

//通过标准输入设备输入串以链式存储存储数据并返回链的头指针。

LString *head, *tail, *p;

int curlen=0;

char ch;

head=(LString*)malloc(sizeof(LString));//建立头指针。

if(!head) {

printf("存储分配失败");

exit(0);

}//存储分配失败。

scanf("%c",&ch);

while(ch!='\n'){

p=(LString*)malloc(sizeof(LString));

if(!p){

printf("存储分配失败");

exit(0);

}//存储分配失败。

p->data=ch;

p->next=NULL;

if(curlen==0) head->next=p;

else{

tail->next=p;

}

tail=p;

++curlen;

head->data=curlen;//用头指针存储串的长度

scanf("%c",&ch);

}

return head;

}//Inpute

3.2 利用Output（）函数输出串。

void Output(LString *T){

//在标准输出设备上输出串T。

LString *p;

p=T->next;

while(p!= NULL)

{

printf("%c",p->data);

p=p->next;

}

printf("\n");

}//Output

3.3 求各串的长度

Length（）函数求的各串的长度，利用一个while循环语句，为后面的函数做好准备工作；int Length(LString *T){

//求串T的长度并返回其值。

int n=0;

LString *head;

head=T;

if(head)

n=head->data;

return n;

}//Length

3.4 求模式串的模式值next[]函数

用《模式匹配的KMP算法》当主串和模式串匹配不相等是，模式串应向右移动一段距离，此时我们需要得到模式串的next函数值。

如何求next函数，next函数值仅取决于模式本身而和主串无关。我们可以从分析next函数的定义出发用递推的方法求得next函数值。由定义知：next[1]=0设next[j]=k，即有：＂t1 t2 … tk-1 ＂ =＂tj-k+1 tj-k+2 … tj-1 next[j+1]=?　可能有两种情况：一种情况：若tk ＝tj 则表明在模式串中这就是说next[j+1]=k+1，即next[j＋１]=next[j]+1 第二种情况：若tk ≠tj 则表明在模式串中t1 t2 … tk ＂≠＂tj-k+1 tj-k+2 … tj ＂此时可把求next函数值的问题看成是一个模式匹配问题，整个模式串既是主串又是模式，而当前在匹配的过程中，已有(4.6)式成立，则当tk ≠tj 时应将模式向右滑动，使得第next[k]个字符和“主串”中的第j个字符相比较。若next[k]=k′，且t k′＝tj，则说明在主串中第j+1个字符之前存在一个最大长度为k′的子串，使得＂t1 t2 … t k′ ＂=＂tj-k′+1 tj- k′+2 … tj ＂ 此： next[j+1]=next[k]+1

同理若t k′ ≠tj，则将模式继续向右滑动至使第next[k′]个字符和tj 对齐，依此类推，直至tj 和模式中的某个字符匹配成功或者不存在任何 k′(1< k′

综上所述，求next函数值过程的伪码算法如下：

void Get_next(SString T,int next[]){

//求模式串T的next函数并存入数组next。

i = 1；next[1] = 0; j = 0;

while (i

if(j= =0 || t[i] = = t[j])

{

++i; ++j; next[i] = j;

}

else j= next[j];

}

}//Get_next

3.5 模式匹配KMP算法的实现：

KMP算法的思想：主串s，模式t希望某趟在si和tj匹配失败后，指针i不回溯，模式t向右“滑动”至某个位置上，使得tk 对准 s i 继续向右进行。显然，现在问题的关键是串t“滑动”到哪个位置上？不妨设位置为k，即si和tj匹配失败后，指针i不动，模式t向右“滑动”，使tk和si对准继续向右进行比较，要满足这一假设，就要有如下关系成立：＂t1 t2 … tk-1 ＂ =＂si-k+1 si-k+2 … si-1 ＂ (4.1)式左边是tk前面的k-1个字符，右边是si 前面的k-1个字符。而本趟匹配失败是在si和tj之处，已经得到的部分匹配结果是：＂t1 t2 … tj-1 ＂ =＂si-j+1 si-j+2 … 　si-1 ＂（4.2）因为k

在求得模式的next函数之后，匹配可如下进行：假设以指针i和j分别指示主串和模式中的比较字符，令i的初值为pos，j的初值为1。若在匹配过程中si≠tj，则i和j分别增１，若si≠tj 匹配失败后，则i不变，j退到next[j]位置再比较，若相等，则指针各自增１，否则j再退到下一个next值的位置，依此类推。直至下列两种情况：一种是j退到某个next值时字符比较相等，则i和j分别增１继续进行匹配; 另一种是j退到值为零（即模式的第一个字符失配），则此时i和j也要分别增１，表明从主串的下一个字符起和模式重新开始匹配。

KMP算法如下：int Index_KMP(SString S,SString T,int pos,int next[]) {

// 利用模式串T的next函数求T在主串S中第pos个字符之后的位置的

// KMP算法。其中，T非空。,1≤pos≤StrLength(S)。

i = pos; 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;

} // Index_KMP

4 测试与分析

4.1若匹配成功：调试结果如下图所示

图4.1

4.2 若匹配不成功：调试结果如下所示

图4.2

5 总结

通过此次模式匹配中的KMP算法的实现的课设，我认识到自己在以前的课程学习中还有很多的不足。在课设中，我了解到各种算法对软件设计的重要性，它能帮助程序设计者设计出更好的程序为人们的日常生活提供了更大的帮助。本次课设在平时的字符的查找中发挥了重要作用。这次课设让我对C语言又复习了一遍。

6 附录：源程序清单

#include

#include

#include

typedef struct LString {

//串的链式存储表示。

char data;

struct LString *next;

}LString;

LString *Input(){

//通过标准输入设备输入串以链式存储存储数据并返回链的头指针。

LString *head, *tail, *p;

int curlen=0;

char ch;

head=(LString*)malloc(sizeof(LString));//建立头指针。

if(!head) {

printf("存储分配失败");

exit(0);

}//存储分配失败。

scanf("%c",&ch);

while(ch!='\n')

{

p=(LString*)malloc(sizeof(LString));

if(!p){

printf("存储分配失败");

exit(0);

}//存储分配失败。

p->data=ch;

p->next=NULL;

if(curlen==0) head->next=p;

else{

tail->next=p;

}

tail=p;

++curlen;

head->data=curlen;//用头指针存储串的长度

scanf("%c",&ch);

}

return head;

}//Inpute

void Output(LString *T){

//在标准输出设备上输出串T。

LString *p;

p=T->next;

while(p!= NULL)

{

printf("%c",p->data);

p=p->next;

}

printf("\n");

}//Output

int Length(LString *T){

//求串T的长度并返回其值。

int n=0;

LString *head;

head=T;

if(head)

n=head->data;

return n;

}//Length

void Get_next(LString *T,int next[]){

//求模式串T的next函数并存入数组next。

int i=1;

int j=0;

int k;

char t[100];

LString *p;

p=T;

for(k=0;k<=Length(T);k++) //将串T的链式存储转换为顺序存储并存入数组t。

{

t[k]=p->data;

p=p->next;

}

next[1]=0;

while (i

if(j==0 || t[i]== t[j])

{

++i; ++j; next[i] = j;

}

else j= next[j];

}

next[i+1]='\n';

}//Get_next

int Index_KMP(LString *S, LString *T,int pos,int next[]) {

// 利用模式串T的next函数求T在主串S中第pos个字符之后的位置的

// KMP算法。其中，T非空。,1≤pos≤StrLength(S)。

int i = pos;

int j = 1;

int k;

LString *p,*q;

char s[255],t[255];

p=S;

q=T;

for(k=0;k<=Length(S);k++) //将串S的链式存储转换为顺序存储

{

s[k]=p->data;

p=p->next;

}

for(k=0;k<=Length(T);k++) //将串T的链式存储转换为顺序存储

{

t[k]=q->data;

q=q->next;

}

while (i <= Length(S) && j <= Length(T)) {

if (j == 0 || s[i] == t[j]) { // 继续比较后继字符

++i; ++j;

} else j = next[j]; // 模式串向右移动

}

if (j > t[0]) return i-t[0]; // 匹配成功

else return 0;

} // Index_KMP

void main()

{

system("cls");

system("color 1f");

system("mode con: cols=78 lines=35");

printf(" ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━┓\n");

printf(" ┃㊣必做题4：KMP算法㊣┃\n");

printf(" ┃姓名：xxxx┃\n");

printf(" ┃学号：xxxxxxxxxx┃\n");

printf(" ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━┛\n");

int Loc, Next[255], pos=0,i=1,j=1;

LString *A,*B;

printf("输入执行KMP算法的模式串A并以ENTER键结束:\n模式串:");

A=Input();//从标准输入设备接收模式串。

printf("输入执行KMP算法主串B并以ENTER键结束:\n主串:");

B=Input();//从标准输入设备接收主串。

printf("\n");

printf("输入执行KMP算法从主串开始的位置并以ENTER键结束:\npos=");

scanf("%d",&pos);//从标准输入设备接收在主串执行KMP算法的开始位置。

while(pos<1)//判断输入是否正确。

{

printf("输入错误请重新输入执行KMP算法的位置:\npos=");

scanf("%d",&pos);

}

printf("\n\n匹配结果如下:\n");//将结果输出到标准输出设备上。

printf("---------------------------------------------匹配结果-------------------------------------------\n\n");

Get_next(A,Next);//调用Get_next函数。

Loc=Index_KMP(B,A,pos,Next);//调用Index_KMP函数并用Loc接收其函数值。

printf("对A执行Next函数的值:\n\t\t\t");//将next输出到标准输出设备上。

for(i=1;Next[i]!='\n';i++)

printf("%d ",Next[i]);

if(Loc!=0){

printf("\n模式串在主串的第%d位置:\n\n",Loc);

printf("\t\t\t");

Output(B);

printf("\t\t\t");

while(j

printf(" ");

++j;

}

Output(A);}

else printf(" \t\t\t匹配失败\n\n");

if(Loc==0)

printf("------------------------------------------匹配失败-------------------------------------\n");

else printf("--------------------------------------匹配成功--------------------------------------\n");

}//main

参考文献:

[1]严蔚敏 吴伟民.数据结构（c语言版）.北京.清华出版社.2008

[2] 谭浩强.C程序设计（第三版）.北京.清华大学出版社.2008[

数据结构-KMP算法的实现