实验7、字符串查找
目的
掌握字符串模式匹配的经典算法。
问题描述
分别用简单方法和KMP方法实现index在文本串中查找指定字符串的功能。
步骤
1. 定义字符串类型
2. 实现简单的index操作，从文本串中查找指定字符串。
3. 实现KMP方法的index操作，从文本串中查找指定字符串。
4. [选]建立一个文本文件，读入每一行来测试自己完成的练习，观察并理解程序的各个处理。
设备和环境
PC计算机、Windows操作系统、C/C++开发环境
结论
能够理解和掌握字符串模式匹配的典型算法。
思考题
1. 对KMP算法分别用手工和程序对某个模式串输出next和nextval。
朴素算法：
#include<stdio.h>
#include<string.h>
#define NOTFOUND -1
#define ERROR -2
#define MAXLEN 100 //字符串的最大长度
char S[MAXLEN+10],T[MAXLEN+10],st[MAXLEN+10]; //串S和串T
int S0,T0; //S0：串S的长度 T0：串T的长度
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 one.nn");
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<stdio.h>
#include<string.h>
#define NOTFOUND -1
#define ERROR -2
#define MAXLEN 100 //字符串的最大长度
char S[MAXLEN+10],st[MAXLEN+10]; //串S和串T
int S0,T0; //S0：串S的长度 T0：串T的长度
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) //如果字符串的长度大于规定的字符串最大长度
{
printf("This String is too long,Please Input a new one.nn");
goto New_Input; //重新读入字符串
}
for (i=1;i<=len;i++) S[i]=st[i-1];
S[len+1]=' ';
S0=len;
}
void Get_next(char *S,int *next)
{
int i=1,j=0;
next[1]=0;
while (i<T0)
if (j==0 || T[i]==T[j]) {i++; j++; next[i]=next[j];}
else j=next[j];
}
int Index_KMP(char *S,int pos)
{
int i=pos,j=1;
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,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,ret);
return 0;
}
扩张KMP：
#include<stdio.h>
#include<string.h>
#define NOTFOUND -1
#define ERROR -2
#define MAXLEN 100 //字符串的最大长度
char S[MAXLEN+10],T0; //S0：串S的长度 T0：串T的长度
int pos; //pos的起始位置
int nextval[MAXLEN+10];
void Init(char *S,Please Input a new one.nn");
goto New_Input; //重新读入字符串
}
for (i=1;i<=len;i++) S[i]=st[i-1];
S[len+1]=' ';
S0=len;
}
void Get_nextval(char *S,int *nextval)
{
int i=1,j=0;
nextval[1]=0;
while (i<T0)
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,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,&pos);
Get_nextval(T,nextval);
ret=Index_KMP(S,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,ret);
return 0;
}
