數(shù)據(jù)結(jié)構(gòu) 尋找最小公共子串

2/6數(shù)據(jù)結(jié)構(gòu)上機(jī)報告——找出最長公共子串?實(shí)驗(yàn)描述：給定串T=t1t2……tn，則串，（即T中順序、連續(xù)的一部分）稱為串T的子串。例如“sing”、“ua”和“Tsinghua”都是字符串“Tsinghua”的子串，而“Thu”和“xyz”不是。若串同時是多個串的子串，則稱為的公共子串。結(jié)合課上所學(xué)的算法設(shè)計思想，設(shè)計算法，對于給定的兩個字符串，找出長度最長的公共子串。?算法描述：按照題目要求，需要找出兩個字符串的最大公共字串。我設(shè)計的算法為用一個矩陣（intIs_equal[][]）來記錄兩個字符串的所有字符之間的匹配情況，如果不匹配則即為0，否則不為0，而這里的計數(shù)規(guī)則下面將繼續(xù)進(jìn)行說明。從上面的敘述中可以知道，當(dāng)用矩陣來記錄兩個字符串的匹配情況時，如果出現(xiàn)匹配字串，那么在矩陣中一定是在對角線的位置，而最長的對角線即對應(yīng)最長的字符字串。在構(gòu)造矩陣的時候，如果出現(xiàn)字符匹配那么就按照語句Is_equal[i][j]=Is_equal[i-1][j-1]+1給矩陣元素賦值，即匹配位置的元素的大小為其左上角元素加1。用一個變量max_len來記錄最長字串的長度，另一個變量flag_x記錄最長字串中的最后一個字符在字符串1中的位置。這樣，在構(gòu)造完矩陣之后也就找到了最長的字串。?復(fù)雜度分析：由上面算法描述中的分析可以知道，該算法的時間復(fù)雜度即為構(gòu)造矩陣的時間復(fù)雜度，兩重循環(huán)，總時間復(fù)雜度為。其實(shí)在些這個代碼的過程中我最開始并未采用上述算法，我在構(gòu)建矩陣的時候是按照出現(xiàn)匹配則賦值為1，否則賦值為0。這樣得到的最終矩陣中0的位置是不匹配的位置，1的位置則是匹配的位置。但是構(gòu)造完矩陣之后并不能立刻得到最長字串，這是還需再次遍歷矩陣尋找最長的對角線。這時時間復(fù)雜度出了構(gòu)造矩陣之外還有遍歷矩陣所花銷的時間，為上面復(fù)雜度的兩倍，即。后面進(jìn)過改進(jìn)后，發(fā)現(xiàn)其實(shí)只需要在構(gòu)造矩陣的時候增加兩個記錄變量，記錄所找到的最長字串的位置，那么在構(gòu)造完矩陣之后就可以得到最長字串。?實(shí)驗(yàn)中遇到的問題：這次實(shí)驗(yàn)相對來說比較容易，思路來得也比較快。在實(shí)驗(yàn)過程中主要遇到的問題就是在給矩陣賦值的時候開始沒有考慮到要單獨(dú)將i=0或j=0的元素拿出來單獨(dú)討論，以致出現(xiàn)數(shù)組越界的情況，后來發(fā)現(xiàn)之后及時解決了問題。其他的基本沒有遇到太詭異的情況了。核心代碼：if(str1[i]==str2[j]) { if(j==0||i==0)//為避免出現(xiàn)Is_equal[-1][j]或Is_equal[i][-1]或Is_equal[-1][-1]的情況發(fā)生，邊界處的元素單獨(dú)討論 { Is_equal[i][j]=1; if(Is_equal[i][j]>max_len) { max_len=Is_equal[i][j];//如果當(dāng)前的字串長度大于已經(jīng)找到的字串長度，更新字串長度 flag_x=i;//更新當(dāng)前最長字串最后一個元素在str1中的位置 } } else { Is_equal[i][j]=Is_equal[i-1][j-1]+1;//出現(xiàn)匹配時，該處的元素的值等于左上角元素值加 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;//記錄所發(fā)現(xiàn)的最長斜線的的最后一個元素的橫坐標(biāo); 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)//為避免出現(xiàn)Is_equal[-1][j]或Is_equal[i][-1]或Is_equal[-1][-1]的情況發(fā)生，邊界處的元素單獨(dú)討論 { Is_equal[i][j]=1; if(Is_equal[i][j]>max_len) { max_len=Is_equal[i][j];//如果當(dāng)前的字串長度大于已經(jīng)找到的字串長度，更新字串長度 flag_x=i;//更新當(dāng)前最長字串最后一個元素在str1中的位置 } } else { Is_equal[i][j]=Is_equal[i-1][j-1]+1;//出現(xiàn)匹配時，該處的元素的值等于左上角元素值加 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';//標(biāo)記字符串末尾 //讀入字符串 count=0; str2[count]=infile.get(); while(str2[count]!=EOF) { count++; str2[count]=infile.get(); } count++; str2[count]='\n';//標(biāo)記字符串末尾}//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