数据结构 寻找最小公共子串

2/6数据结构上机报告——找出最长公共子串☞实验描述：给定串T=t1t2……tn，则串，（即T中顺序、连续的一部分）称为串T的子串。例如“sing”、“ua”和“Tsinghua”都是字符串“Tsinghua”的子串，而“Thu”和“xyz”不是。若串同时是多个串的子串，则称为的公共子串。结合课上所学的算法设计思想，设计算法，对于给定的两个字符串，找出长度最长的公共子串。☞算法描述：按照题目要求，需要找出两个字符串的最大公共字串。我设计的算法为用一个矩阵（intIs_equal[][]）来记录两个字符串的所有字符之间的匹配情况，如果不匹配则即为0，否则不为0，而这里的计数规则下面将继续进行说明。从上面的叙述中可以知道，当用矩阵来记录两个字符串的匹配情况时，如果出现匹配字串，那么在矩阵中一定是在对角线的位置，而最长的对角线即对应最长的字符字串。在构造矩阵的时候，如果出现字符匹配那么就按照语句Is_equal[i][j]=Is_equal[i-1][j-1]+1给矩阵元素赋值，即匹配位置的元素的大小为其左上角元素加1。用一个变量max_len来记录最长字串的长度，另一个变量flag_x记录最长字串中的最后一个字符在字符串1中的位置。这样，在构造完矩阵之后也就找到了最长的字串。☞复杂度分析：由上面算法描述中的分析可以知道，该算法的时间复杂度即为构造矩阵的时间复杂度，两重循环，总时间复杂度为。其实在些这个代码的过程中我最开始并未采用上述算法，我在构建矩阵的时候是按照出现匹配则赋值为1，否则赋值为0。这样得到的最终矩阵中0的位置是不匹配的位置，1的位置则是匹配的位置。但是构造完矩阵之后并不能立刻得到最长字串，这是还需再次遍历矩阵寻找最长的对角线。这时时间复杂度出了构造矩阵之外还有遍历矩阵所花销的时间，为上面复杂度的两倍，即。后面进过改进后，发现其实只需要在构造矩阵的时候增加两个记录变量，记录所找到的最长字串的位置，那么在构造完矩阵之后就可以得到最长字串。☞实验中遇到的问题：这次实验相对来说比较容易，思路来得也比较快。在实验过程中主要遇到的问题就是在给矩阵赋值的时候开始没有考虑到要单独将i=0或j=0的元素拿出来单独讨论，以致出现数组越界的情况，后来发现之后及时解决了问题。其他的基本没有遇到太诡异的情况了。核心代码：if(str1[i]==str2[j]) { if(j==0||i==0)//为避免出现Is_equal[-1][j]或Is_equal[i][-1]或Is_equal[-1][-1]的情况发生，边界处的元素单独讨论 { Is_equal[i][j]=1; if(Is_equal[i][j]>max_len) { max_len=Is_equal[i][j];//如果当前的字串长度大于已经找到的字串长度，更新字串长度 flag_x=i;//更新当前最长字串最后一个元素在str1中的位置 } } else { Is_equal[i][j]=Is_equal[i-1][j-1]+1;//出现匹配时，该处的元素的值等于左上角元素值加 if(Is_equal[i][j]>max_len) { max_len=Is_equal[i][j]; flag_x=i; } } } else Is_equal[i][j]=0;//源代码//LCS.h#include<iostream>#include<string>usingnamespacestd;voidLCS(char*str1,char*str2,intstr1_len,intstr2_len,ofstream&outfile){ int**Is_equal;//记录串和串的匹配情况的矩阵 Is_equal=newint*[str1_len]; for(inti=0;i<str1_len;i++) { Is_equal[i]=newint[str2_len]; } intflag_x=0;//记录所发现的最长斜线的的最后一个元素的横坐标; intmax_len=0;//记录最长公共字符串的长度 for(inti=0;i<str1_len;i++) { for(intj=0;j<str2_len;j++) { if(str1[i]==str2[j]) { if(j==0||i==0)//为避免出现Is_equal[-1][j]或Is_equal[i][-1]或Is_equal[-1][-1]的情况发生，边界处的元素单独讨论 { Is_equal[i][j]=1; if(Is_equal[i][j]>max_len) { max_len=Is_equal[i][j];//如果当前的字串长度大于已经找到的字串长度，更新字串长度 flag_x=i;//更新当前最长字串最后一个元素在str1中的位置 } } else { Is_equal[i][j]=Is_equal[i-1][j-1]+1;//出现匹配时，该处的元素的值等于左上角元素值加 if(Is_equal[i][j]>max_len) { max_len=Is_equal[i][j]; flag_x=i; } } } else Is_equal[i][j]=0; } } if(max_len==0) { cout<<"0\n"; outfile<<"0\n"; } else { outfile<<max_len<<endl; cout<<max_len<<endl; for(intk=flag_x-max_len+1;k<=flag_x;k++) { cout<<str1[k]; outfile<<str1[k]; } cout<<endl; outfile<<endl; }}//Readinfile.h#include<iostream>#include<fstream>#include<string>usingnamespacestd;voidReadinfile(ifstream&infile,char*str1,char*str2){ //读入字符串 intcount=0; str1[count]=infile.get(); while(str1[count]!='\n') { count++; str1[count]=infile.get(); } count++; str1[count]='\n';//标记字符串末尾 //读入字符串 count=0; str2[count]=infile.get(); while(str2[count]!=EOF) { count++; str2[count]=infile.get(); } count++; str2[count]='\n';//标记字符串末尾}//main.cpp#include<iostream>#include<string>#include<fstream>#include"Readinfile.h"#include"LCS.h"usingnamespacestd;intmain(intargc,char*argv[]){ if(argc!=3) { cout<<"Usage:*.exe<input.txt><output.txt>"<<endl; return0; } ifstreaminfile(argv[1],ios_base::in);//infile为输入流文件对象 if(!infile.is_open()) { cout<<"openinfilefail!"<<endl; return0; } ofstreamoutfile(argv[2],ios_base::out);//outfile为输出流文件对象 if(!outfile.is_open()) { cout<<"openoutfilefail!"<<endl; return0; } charstr1[4000],str2[4000];//字符串长度短于 intstr1_len=0,str2_len=0;//分别记录两个字符串的长度 Readinfile(i