2023年7月20日发(作者：)

实验7、字符串查找

目的

掌握字符串模式匹配的经典算法。

问题描述

分别用简单方法和KMP方法实现index在文本串中查找指定字符串的功能。

步骤

1.

定义字符串类型

2.

实现简单的index操作，从文本串中查找指定字符串。

3.

实现KMP方法的index操作，从文本串中查找指定字符串。

4.

[选]建立一个文本文件，读入每一行来测试自己完成的练习，观察并理解程序的各个处理。

设备和环境

PC计算机、Windows操作系统、C/C++开发环境

结论

能够理解和掌握字符串模式匹配的典型算法。

思考题

1.

对KMP算法分别用手工和程序对某个模式串输出next和nextval。

朴素算法：

#include

#include

#define

NOTFOUND -1 #define

ERROR -2

#define

MAXLEN 100 //字符串的最大长度

char

S[MAXLEN+10],T[MAXLEN+10],st[MAXLEN+10];

S和串T

//串int

S0,T0;

T的长度

//S0：串S的长度 T0：串int

pos;

//pos的起始位置

void

Init(char *S,int &S0)//读入字符串

{

int len,i;

New_Input:

scanf("%s",st); //读入字符串

len=strlen(st);

if (len>MAXLEN) //如果字符串的长度大于规定的字符串最大长度

{

printf("This String is too long,Please Input a new ");

goto New_Input; //重新读入字符串 }

for (i=1;i<=len;i++) S[i]=st[i-1];

S[len+1]='';

S0=len;

}

int

Index(char *S,char *T,int pos)

{

if (pos<1 || pos>S0) return ERROR;

//

输入数据不合法

int i=pos,j=1;

while (i<=S0 && j<=T0)

{

if (S[i]==T[j]) {i++; j++;}

else {i=i-j+2; j=1;} //不匹配时，对应S移到下一位进行匹配

}

if (j>T0) return i-T0;

//返回S中找到的位置 }

else return NOTFOUND;

int

main()

{

int ret;//函数返回值

Init(S,S0);

Init(T,T0);

scanf("%d",&pos);

ret=Index(S,T,pos); //在S串中从pos这个位置起，找到第一个与T匹

配的子串的起始位置

if (ret==NOTFOUND) printf("Not Found.n");

else if (ret==ERROR) printf("The Input Data is Error.n");

else printf("In S,from %dth is equal to T.n",ret);

return 0;

}

KMP：

#include #include

#define

NOTFOUND -1

#define

ERROR -2

#define

MAXLEN 100 //字符串的最大长度

char

S[MAXLEN+10],T[MAXLEN+10],st[MAXLEN+10];

//串S和串T

int

S0,T0;

T的长度

//S0：串S的长度 T0：串int

pos;

//pos的起始位置

int

next[MAXLEN+10];

void

Init(char *S,int &S0)//读入字符串

{

int len,i;

New_Input:

scanf("%s",st); //读入字符串

len=strlen(st);

if (len>MAXLEN) //如果字符串的长度大于规定的字符串最大长度

}

{

}

for (i=1;i<=len;i++) S[i]=st[i-1];

S[len+1]='';

S0=len;

printf("This String is too long,Please Input a new ");

goto New_Input; //重新读入字符串

void

Get_next(char *S,int *next)

{

}

int

Index_KMP(char *S,char *T,int pos)

{

int i=pos,j=1;

int i=1,j=0;

next[1]=0;

while (i

if (j==0 || T[i]==T[j]) {i++; j++; next[i]=next[j];}

else j=next[j];

}

while (i<=S0 && j<=T0)

if (j==0 || S[i]==T[j]) {i++; j++;}

else j=next[j];

if (j>T0) return i-T0;

else return NOTFOUND;

int

main()

{

int ret;//函数返回值

Init(S,S0);

Init(T,T0);

scanf("%d",&pos);

Get_next(T,next);

ret=Index_KMP(S,T,pos); //在S串中从pos这个位置起，找到第一个与T匹配的子串的起始位置

if (ret==NOTFOUND) printf("Not Found.n");

else if (ret==ERROR) printf("The Input Data is Error.n");

else printf("In S,from %dth is equal to T.n",ret);

return 0; }

扩张KMP：

#include

#include

#define

NOTFOUND -1

#define

ERROR -2

#define

MAXLEN 100 //字符串的最大长度

char

S[MAXLEN+10],T[MAXLEN+10],st[MAXLEN+10];

int

S0,T0;

的长度

int

pos; //pos的起始位置

//串S和串T

//S0：串S的长度 T0：串Tint

nextval[MAXLEN+10];

void

Init(char *S,int &S0)//读入字符串

{

int len,i;

New_Input:

scanf("%s",st); //读入字符串

len=strlen(st);

if (len>MAXLEN) //如果字符串的长度大于规定的字符串最大长度

}

{

}

for (i=1;i<=len;i++) S[i]=st[i-1];

S[len+1]='';

S0=len;

printf("This String is too long,Please Input a new ");

goto New_Input; //重新读入字符串

void

Get_nextval(char *S,int *nextval)

{

int i=1,j=0;

nextval[1]=0;

while (i

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(char *S,char *T,int pos)

{

int i=pos,j=1;

while (i<=S0 && j<=T0)

if (j==0 || S[i]==T[j]) {i++; j++;} else j=nextval[j];

if (j>T0) return i-T0;

else return NOTFOUND;

}

int

main()

{

int ret;//函数返回值

Init(S,S0);

Init(T,T0);

scanf("%d",&pos);

Get_nextval(T,nextval);

ret=Index_KMP(S,T,pos); //在S串中从pos这个位置起，找到第一个与T匹配的子串的起始位置

}

if (ret==NOTFOUND) printf("Not Found.n");

else if (ret==ERROR) printf("The Input Data is Error.n");

else printf("In S,from %dth is equal to T.n",ret);

return 0;