实验顺序串的各种模式匹配运算 有理数混合运算顺序

顺序串的各种模式匹配运算

编写一个程序,实现顺序串的各种模式匹配运算,并在此基础上完成如下功能:

(1)建立“abcabcdabcdeabcdefabcdefg”目标串s和“abcdeabcdefab”模式串t。

(2)采用简单匹配算法求t在s中的位置。

(3)由模式串t求出next值和nextval值。

(4)采用KMP算法求t在s中的位置。

(5)采用改进的KMP算法求t在s中的位置。

#include<stdio.h>
#include<string.h>
#include<malloc.h>

#define MaxSize 100

typedef struct {
chardata[MaxSize];//定义可容纳MaxSize个字符的空间
intlength;//标记当前实际串长
}SqString;

void StrAssign(SqString &str,charcstr[]){ //由串常量cstr创建串str
int i;
for(i=0;cstr[i]!='';i++)
str.data[i]=cstr[i];
str.length=i;
}

void DispStr(SqStrings){ //输出串s的所有元素
int i;
if(s.length>0){
for(i=0;i<s.length;i++)
printf("%c",s.data[i]);
printf("n");
}
}

int Index(SqString s,SqStringt){//简单匹配算法
inti=0,j=0,k;
while(i<s.length &&j<t.length){
if(s.data[i]==t.data[j]){//继续匹配下一个字符
i++;
j++;
}else{//主串、子串指针回溯重新开始下一次匹配
i=i-j+1;
j=0;
}
}
if(j>=t.length)
k=i-t.length;//返回匹配的第一个字符的下标
else
k=-1;//模式匹配不成功
returnk;
}

void GetNext(SqString t,intnext[]){//由模式串t求出next值
intj,k;
j=0;
k=-1;next[0]=-1;
while(j<t.length-1){
if(k==-1 || t.data[j]==t.data[k]){
j++;
k++;
next[j]=k;
}else
k=next[k];
}
}

void GetNextval(SqString t,intnextval[]){//由模式串t求出nextval值
intj=0,k=-1;
nextval[0]=-1;
while(j<t.length){
if(k==-1 || t.data[j]==t.data[k]){
j++;
k++;
if(t.data[j]!=t.data[k])
nextval[j]=k;
else
nextval[j]=nextval[k];
}else
k=nextval[k];
}
}

int KMPIndex(SqString s,SqStringt){//KMP算法
intnext[MaxSize],i=0,j=0,v;
GetNext(t,next);
while(i<s.length &&j<t.length){
if(j==-1 || s.data[i]==t.data[j]){
i++;
j++;
}else
j=next[j]; //i不变,j后退
}
if(j>=t.length)
v=i-t.length;//返回匹配模式串的首字符下标
else
v=-1;//返回不匹配标志
returnv;
}

int KMPIndex1(SqString s,SqStringt){ //改进的KMP算法
intnextval[MaxSize],next[MaxSize],i=0,j=0,v;
GetNextval(t,next);
GetNextval(t,nextval);
while(i<s.length &&j<t.length){
if(j==-1 || s.data[i]==t.data[j]){
i++;
j++;
}else
j=nextval[j];
}
if(j>=t.length)
v=i-t.length;//返回匹配模式串的首字符下标
else
v=-1;
实验顺序串的各种模式匹配运算 有理数混合运算顺序
returnv;
}

int main(){
int j;
intnext[MaxSize],nextval[MaxSize];
SqStrings,t;
StrAssign(s,"abcabcdabcdeabcdefabcdefg");
StrAssign(t,"abcdeabcdefab");
printf("串s:");DispStr(s);
printf("串t:");DispStr(t);
printf("简单匹配P算法:n");
printf(" t在s中的位置=%dn",Index(s,t));
GetNext(t,next);//由模式串t求出next值
GetNextval(t,nextval); //由模式串t求出nextval值
printf("j ");
for(j=0;j<t.length;j++)
printf("M",j);
printf("n");
printf("t[j] ");
for(j=0;j<t.length;j++)
printf("L",t.data[j]);
printf("n");
printf("next ");
for(j=0;j<t.length;j++)
printf("M",next[j]);
printf("n");
printf("nextval");
for(j=0;j<t.length;j++)
printf("M",nextval[j]);
printf("n");
printf("KMP算法:n");
printf(" t在s中的位置=%dn",KMPIndex(s,t));
printf("改进的KMP算法:n");
printf(" t在s中的位置=%dn",KMPIndex1(s,t));
return0;
}

  

爱华网本文地址 » http://www.413yy.cn/a/25101017/339948.html

更多阅读

KMP模式匹配算法中next和nextval的求解 kmp next

KMP算法是模式匹配专用算法。它是在已知模式串的next或nextval数组的基础上执行的。如果不知道它们二者之一,就没法使用KMP算法,因此我们需要计算它们。KMP算法由两部分组成:第一部分,计算模式串的next或nextval数组。第二部分,利用

新浪的盈利模式分析 新浪盈利模式

新浪盈利模式分析实验报告一、 实验目的与要求实验目的:了解中文门户网站新浪的特点,分析这个网站的商业模式;分析他的收入模式、分析收入流的组合模式和利润途径。分析传递客户价值的方式和方法。实验要求:1、新浪的收入模式分析描述

悬式绝缘子串的安装 悬式绝缘子串

悬式绝缘子串的安装应符合下列要求:一、除设计原因外,悬式绝缘子串应与地面垂直,当受条件限制不能满足要求时,可有不超过5°的倾斜角。二、多串绝缘子并联时,每串所受的张力应均匀。三、绝缘子串组合时,联结金具的螺栓、销钉及锁紧销等必

声明:《实验顺序串的各种模式匹配运算 有理数混合运算顺序》为网友思念埋在发间分享!如侵犯到您的合法权益请联系我们删除