【数据结构】实验七：字符串

实验七 字符串实验报告

一、实验目的与要求

1）巩固对串的理解；

2）掌握串的基本操作实现；

3）掌握 BF 和 KMP 算法思想。

二、实验内容

1. 给定一个字符串ababcabcdabcde和一个子串abcd,查找字串是否在主串中出现。出现就返回主串中的第一个匹配下标，没有则返回-1。本题采用BF串匹配算法。

2.编写一个函数,计算一个子串在一个主串中出现的次数,如果该子串不出现,则返回0。本题考虑子串重叠,如:子串为aa,主串为aaa,考虑子串重叠结果为2,不考虑子串重叠结果为1。

示列1：输入："ababab","abababab"    返回值：2

示列2：输入："abab","abacabab"  返回值：1

提示：

首先进行特殊情况判断，如果模式串长度大于主串，或者主串为空，返回0。

然后分别遍历主串和模式串，只要当前字符相等，模式串和主串均后移一位，如果不相等，模式串重新回退到索引0的位置。

当模式串索引达到长度m时，说明全部匹配上了。此时将匹配次数加一，同时主串索引i回退到上次匹配开头的下一位，模式串索引j回到0。

采用kmp算法

三、实验结果

1）请将调试通过的运行结果截图粘贴在下面，并说明测试用例和运行过程，简述算法思想。

2）请将源代码cpp文件和实验报告一起压缩上传。

---

实验1

运行结果：

 

 

算法思想：

BF算法的思想主要如下：在主串和子串中设置比较的下标i和j（本段代码中初始化均为0）。循环比较直到主串中所剩字符个数小于子串的长度，或者是子串的所有字符均比较完。如果主串A和子串B满足A[i]=B[i]，那么继续比较子串和主串的下一个字符；否则，将i和j回溯，准备下一趟的比较。如果子串中的所有字符均比较完，那么说明匹配成功，返回匹配的起始比较下标；否则，说明匹配失败，按照题目要求返回-1。

实验代码：

#include <iostream>#include <cstdio>#include <cstring>using namespace std;//BF串匹配算法int bf(char *strA, char *strB){//strA是主串，strB是子串int i=0,j=0;int lena=strlen(strA);//主串的长度int lenb=strlen(strB);//子串的长度while(i<lena && j<lenb){if(strA[i]==strB[j]){i++;j++;}else{i=i-j+1;//如果i、j初始值为1，则返回i=i-j+2？j=0;//重置子串的标记位置j}}//跳出循环，遍历完成//判断字串情况if(j==lenb){return i-j+1;//成功匹配}return -1;//不成功匹配}//主函数->调试int main() {//int mybf=bf("ababcabcdabcde","abcd");char strA[1000],strB[1000];//max长度设置为1000cout<<"请输入主串："<<endl;cin>>strA;cout<<"请输入子串："<<endl;cin>>strB;int mybf=bf(strA,strB);if(mybf>0){cout<<"主串中的第一个匹配下标："<<mybf<<endl;}else{cout<<mybf<<endl;}return 0;}

 

实验2

运行结果：

 

 

算法思想：

KMP算法的思想主要如下：在主串A和子串B中设置比较的下标i和j（本段代码中初始化均为0）。循环比较直到主串中所剩字符个数小于子串的长度，或者是子串的所有字符均比较完。如果A[i]=B[j]或j=0，那么继续比较A和B的下一个字符；否则，将j向右滑动到next[i]的位置（j= next[i]），准备下一趟的比较。如果子串中的所有字符均比较完，那么说明匹配成功，返回匹配的起始比较下标；否则，说明匹配失败，按照题目的要求返回0。

实验代码：

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;int next[100];//全局数组变量 //获取next数组 
void getNext(char b[],int next[]){int len=strlen(b);next[0]=-1;int k=-1;int j=0;while(j<len){if(k==-1 || b[k]==b[j]){j++;k++;next[j] = k;}else{k=next[k];}}
}//KMP算法  
int kmp(char *a,char *b){int lena=strlen(a);int lenb=strlen(b);int i=0,n=0,k=0;//n作为计数器 while(i<lena){if(k==-1 || a[i]==b[k]){++i;++k;}else{k=next[k];}if(k==lenb){n++;k=next[k];}}return n;
}int main(){char a[100000],b[10000];//a为主串，b为子串 cout<<"请输入主串："<<endl; cin>>a;cout<<"请输入子串："<<endl; cin>>b;getNext(b,next);cout<<"子串出现次数为："<<kmp(a,b);return 0; 
}

---

其他：

#include<iostream>
using namespace std;struct String{char *elem;int length;
};void Strcpy(String &S,const char str[]){//忌引用数组 ,const!!!int i=0;int str_len=0;while(str[i]!='\0'){str_len++;i++;}//字符串长度 if(!str_len) S.length=0;int k=1,j=0;S.elem=new char[str_len+1];while(k<=str_len)S.elem[k++]=str[j++];S.elem[0]=' ';//0号位随意 S.length=str_len;
}int StrIndex_BF(String &S,String &T,int pos){int i=pos,j=1;while((i<=S.length)&&(j<=T.length)){//while((i<=S.length-T.length+1)&&(j<=T.length))错误！！ if(S.elem[i]==T.elem[j]){i++;j++;}else{i=i-j+2;//回溯操作 j=1;if(i>S.length-T.length+1)break;//S中剩下元素小于T的元素个数 }}if(j>T.length)//T中全部字符均匹配成功！ return (i-T.length);elsereturn -1;
}void Destroy(String &S){delete []S.elem;
}int main(){String S,T; 
//	Strcpy(S,"ababcabcdabcde");//主串 
//	Strcpy(T,"abcd");//模式串Strcpy(S,"ababcabcacbab");//主串 Strcpy(T,"abcac");//模式串 int p=StrIndex_BF(S,T,1);//匹配函数 if(p!=-1)cout<<"匹配成功！主串中的第一个匹配下标为："<<p<<endl;elsecout<<"匹配失败！"<<endl;Destroy(S);Destroy(T);return 0;
}

#include<iostream>
using namespace std;struct String{char* elem;int length;
};void StrCopy(String &s,char a[]){int i=0;int strlen=0;while(a[i]!='\0'){strlen++;i++;}s.elem=new char[strlen+1];int k=1,j=0;while(j<strlen)s.elem[k++]=a[j++];s.elem[0]='\0';s.length=strlen;
}void Get_next(String &T,int (&next)[20]){int i=0,j=1;next[1]=0;while(j<T.length){if(i==0||T.elem[i]==T.elem[j]){i++;j++;next[j]=i;}elsei=next[i];}
}int Strmatch_KMP(String &S,String &T,int next[]){int i=1,j=1,num=0;if(S.length<T.length)return 0;while((i<=S.length)&&(j<=T.length)){//while((i<=S.length-T.length+1)&&(j<=T.length))错误！！ if(j==0||(S.elem[i]==T.elem[j])){i++;j++;}else  j=next[j];if(j>T.length){num++;i=i-j+2;j=1;//回溯if(i>S.length-T.length+1)break;//S中剩下元素小于T的元素个数  }}return num;
}void Destroy(String &S){delete []S.elem;
}int main(){char a[20],b[20];gets(a);gets(b);String S,T;StrCopy(S,a);StrCopy(T,b);int next[20]={0,0,1};//初始化next【i】 Get_next(T,next);//找到对应的k值 int num=Strmatch_KMP(S,T,next);//重叠次数 if(!num) cout<<"子串不在主串中出现！"<<endl;else cout<<"子串在主串中出现，且重叠结果为："<<num<<endl;Destroy(S);Destroy(T);return 0;
}