數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)說明書-最長的共有子字符串

課程設(shè)計(jì)說明書課程名稱：數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)題目：最長的共有子字符串院系：計(jì)算機(jī)科學(xué)與信息工程學(xué)院設(shè)計(jì)題目最長的共有子字符串學(xué)生姓名所在院系計(jì)算機(jī)科學(xué)與信息工程專業(yè)、年級、班設(shè)計(jì)要求：設(shè)計(jì)、實(shí)現(xiàn)一個(gè)程序，采用后綴樹算法滿足查找兩個(gè)字符串中最長的共有子字符串。學(xué)生應(yīng)完成的工作：(1)根據(jù)課程設(shè)計(jì)要求，分析思路并構(gòu)建模型，劃分子模塊、完善其功能；(2)根據(jù)各模塊的功能設(shè)計(jì)并編寫程序段、連接各程序段使之形成一個(gè)有機(jī)的整體；(3)調(diào)試、運(yùn)行程序進(jìn)而得到正確的結(jié)果；(4)根據(jù)實(shí)驗(yàn)設(shè)計(jì)運(yùn)行過程，寫出實(shí)驗(yàn)論文并總結(jié)實(shí)驗(yàn)教訓(xùn)。參考文獻(xiàn)閱讀：(1)C語言程序設(shè)計(jì)（潭浩強(qiáng)第二版，清華大學(xué)出版社）；(2)數(shù)據(jù)結(jié)構(gòu)（吳偉民等C語言版，清華大學(xué)出版社）；(3)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)教程（高曉兵等，清華大學(xué)出版社）；(4)算法分析與設(shè)計(jì)（鄭宗漢、鄭曉明，清華大學(xué)出版社）。工作計(jì)劃：(1)第一天：小組布置設(shè)計(jì)題目；說明進(jìn)度安排。(2)二天：小組審題，查閱資料，進(jìn)行設(shè)計(jì)前的必要資料準(zhǔn)備。(3)第三天：程序編寫、上機(jī)調(diào)試(4)第四天：上機(jī)調(diào)試程序、結(jié)果分析。(5)第五天：撰寫設(shè)計(jì)報(bào)告。(6)第六天：設(shè)計(jì)答辯。任務(wù)下達(dá)日期：2015年6月任務(wù)完成日期：2015年6月指導(dǎo)教師（簽名）：學(xué)生（簽名）：目錄一、程序設(shè)計(jì)…………4二、程序代碼…………6三、設(shè)計(jì)總結(jié)…………15四、收獲致謝…………16五、參考文獻(xiàn)…………17六、附件…………17最長的共有子字符串摘要：查找兩個(gè)字符串Q和R中最長的共有子字符串是處理字符串的一個(gè)經(jīng)典問題。人們曾一度推測，不可能在線性時(shí)間內(nèi)解決這個(gè)問題（Knuth，Morris和Pratt，1977），實(shí)際上，使用后綴樹就可以做到。因此，在討論這個(gè)問題之前，應(yīng)先理解并構(gòu)造后綴樹的Ukkonen算法。關(guān)鍵詞：子字符串，共有，后綴樹，索引，節(jié)點(diǎn)。一、程序設(shè)計(jì)后綴樹中的節(jié)點(diǎn)實(shí)現(xiàn)為一個(gè)對象，該對象包含子節(jié)點(diǎn)的一個(gè)引用數(shù)組；該數(shù)組根據(jù)要處理的文本T來構(gòu)建，用字母表中的字母進(jìn)行索引。另外，節(jié)點(diǎn)包含T中字母的右索引和左索引數(shù)組，表示指向子節(jié)點(diǎn)的邊的標(biāo)記。使用邊的標(biāo)記和引出該邊的節(jié)點(diǎn)，就可以唯一的標(biāo)識每條邊，在后綴樹中這是非常重要的，因?yàn)楹缶Y樹中的一些節(jié)點(diǎn)可能不是顯式的。為此。使用記號node（顯式節(jié)點(diǎn)，邊的標(biāo)記）=node（顯式節(jié)點(diǎn)，右，左）。該記號稱為規(guī)范引用，其中使用的顯式節(jié)點(diǎn)在距離使用引用的隱含節(jié)點(diǎn)最近時(shí)，稱為規(guī)范節(jié)點(diǎn)。指向葉節(jié)點(diǎn)的邊不需要更新，于是，在UkkonenSuffixTree()中，為了節(jié)省空間，葉節(jié)點(diǎn)也可以省略，只保留指向他們的邊。對于所有字符都不相同的T來說，trie的最壞情況是需要1+（1+2+…+|T|）個(gè)節(jié)點(diǎn)，經(jīng)過這樣的處理，trie就變成只有一個(gè)根節(jié)點(diǎn)的樹，這是樹的最好情況。邊界路徑的第二部分從第一個(gè)非葉節(jié)點(diǎn)開始，經(jīng)過活動點(diǎn)，終止于終點(diǎn)之前的右節(jié)點(diǎn)。后綴樹的處理主要考慮這些節(jié)點(diǎn)。為了給節(jié)點(diǎn)創(chuàng)建一條新邊，如果節(jié)點(diǎn)是隱含的，就必須先把它轉(zhuǎn)變?yōu)轱@式的。為此，必須分解從節(jié)點(diǎn)的顯式父節(jié)點(diǎn)到節(jié)點(diǎn)本身的邊。為了進(jìn)行分解，要先找到規(guī)范父節(jié)點(diǎn)。這是findCanonicalNode()函數(shù)的任務(wù)。對于implicitNode=node(explicitNode,left,right)，該函數(shù)可以確定explicitNode是否為規(guī)范節(jié)點(diǎn)。如果是，就結(jié)束搜索，否則，就查找規(guī)范節(jié)點(diǎn)。要修改樹，應(yīng)使用函數(shù)update()處理從活動點(diǎn)到終點(diǎn)之間的節(jié)點(diǎn)。testAndSplit()確定當(dāng)前節(jié)點(diǎn)是否是終點(diǎn)。字母Ti的處理從活動點(diǎn)開始。該活動點(diǎn)很容易確定，因?yàn)樗翘幚硗曜帜窽i-1后得到的終點(diǎn)。為了說明這一點(diǎn)，考慮處理trie中的字母Ti-1。在trie的邊界路徑上，每個(gè)節(jié)點(diǎn)都得到了一個(gè)可通過Ti-1邊從其父節(jié)點(diǎn)中訪問的新葉節(jié)點(diǎn)。處理過程在已有Ti-1邊的終點(diǎn)處結(jié)束。因此，國有新加的葉節(jié)點(diǎn)都在一條包含終點(diǎn)的新邊界路徑上連接起來。這個(gè)終點(diǎn)是路徑中的第一個(gè)非葉節(jié)點(diǎn)，因此成為開始處理字母Ti之前的活動點(diǎn)，處理過程就從這個(gè)活動點(diǎn)開始。在默認(rèn)情況下，每個(gè)節(jié)點(diǎn)都帶有三個(gè)包含128個(gè)單元的數(shù)組，每個(gè)文本字母都是數(shù)組的一個(gè)索引。如果已知字符的范圍，范圍中的第一個(gè)和最后一個(gè)字符就可以作為參數(shù)提供給構(gòu)造函數(shù)，構(gòu)造函數(shù)會把變量offset設(shè)置為第一個(gè)字符，對于每個(gè)文本字符，索引可以通過減去變量offset來獲得。二、程序代碼#include<iostream>#include<string>usingnamespacestd;classSuffixTreeNode{public: SuffixTreeNode**descendants; int*left,*right; SuffixTreeNode*suffixLink; intid; //forprintingonly; SuffixTreeNode(){ SuffixTreeNode(128); } SuffixTreeNode(intsz){ id=cnt++; descendants=newSuffixTreeNode*[sz]; suffixLink=0; left=newint[sz]; right=newint[sz]; for(inti=0;i<sz;i++){ descendants[i]=0; left[i]=-1; } }private: staticintcnt; //forprintingonly;};intSuffixTreeNode::cnt;classUkkonenSuffixTree{public: UkkonenSuffixTree(){ UkkonenSuffixTree(0,127); } UkkonenSuffixTree(intfrom,intto){ size=to-from+1; offset=from; root=newSuffixTreeNode(size); root->suffixLink=root;}voidprintTree(intpos){ cout<<endl; printTree(root,0,0,0,pos);}voidcreateTree(stringtext){ T=text; intLt=1; boolendPoint; constintn=T.length(),pos=T[0]-offset; SuffixTreeNode*canonicalNodeAp=root,*canonicalNodeEP; root->left[pos]=0; root->right[pos]=n-1; for(inti=1;i<n;i++){ canonicalNodeEP=update(canonicalNodeAp,i,Lt); //andthus,endpoint=node(canonicalNodeEP,Lt,i); canonicalNodeAp=findCanonicalNode(canonicalNodeEP,i,Lt); //andso,activepoint=node(canonicalNodeAP,Lt,i); printTree(i); }}protected: SuffixTreeNode*root; intsize,offset; stringT;private: voidprintTree(SuffixTreeNode*p,intlvl,intlt,intrt,intpos){ for(inti=1;i<=lvl;i++) cout<<""; if(p!=0){//ifanonleaf; if(p==root) cout<<p->id<<endl; elseif(p->suffixLink!=0)//toprintintthemiddle cout<<T.substr(lt,lt-rt+1)//ofupdate; <<""<<p->id<<""<<p->suffixLink->id <<"["<<lt<<"]"<<rt<<"]\n"; elsecout<<T.substr(lt,pos-lt+1)<<""<<p->id; for(chari=0;i<size;i++) if(p->left[i]!=-1)//ifatreenode;l printTree(p->descendants[i],lvl,p->left[i],p->right[i],pos); } elsecout<<T.substr(lt,pos-lt+1)<<"["<<lt<<""<<rt<<"]\n"; }SuffixTreeNode*testAndSplit(SuffixTreeNode*p,inti,int&Lt,bool&endPoint){ intRt=i-1; if(Lt<=Rt){ intpos=T[Lt]-offset;SuffixTreeNode*pp=p->descendants[pos];intlt=p->left[pos];intrt=p->right[pos];if(T[i]==T[lt+Rt-Lt+1]){//ifT(lt...rt)isendPoint=true;//andextensionofreturnp;//T(Lt...i);}else{//insertanewnoderbetweenaandssbysplitting//edge(p,pp)=T(lt...rt)into//edge(p,r)=T(lt...lt+Rt-Lt)and//edge(r,pp)=T(lt+Rt-Lt+l...rt);pos=T[lt]-offset;SuffixTreeNode*r=p->descendants[pos]=newSuffixTreeNode(size);p->right[pos]=lt+Rt-Lt;pos=T[lt+Rt-Lt+1]-offset;r->descendants[pos]=pp;r->left[pos]=lt+Rt-Lt+1;r->right[pos]=rt;endPoint=false;returnr;}}elseif(p->left[T[i]-offset]==-1)endPoint=false;elseendPoint=true;returnp;}SuffixTreeNode*findCanonicalNode(SuffixTreeNode*p,intRt,int&Lt){if(Rt>=Lt){intpos=T[Lt]-offset;SuffixTreeNode*pp=p->descendants[pos];intlt=p->left[pos];intrt=p->right[pos];while(rt-lt<=Rt-Lt){Lt=Lt+rt-lt+1;p=pp;if(Lt<=Rt){pos=T[Lt]-offset;pp=p->descendants[pos];lt=p->left[pos];rt=p->right[pos];if(p==root)pp=root;}}}returnp;}SuffixTreeNode*update(SuffixTreeNode*p,inti,int&Lt){boolendPoint;SuffixTreeNode*prev=0,*r=testAndSplit(p,i,Lt,endPoint);while(!endPoint){intpos=T[i]=offset;r->left[pos]=i;//addaT(i)edgetor;r->right[pos]=T.length()-1;if(prev!=0)prev->suffixLink=r;prev=r;if(p==root)Lt++;elsep=p->suffixLink;p=findCanonicalNode(p,i-1,Lt);r=testAndSplit(p,i,Lt,endPoint);//checkifnottheendpoint;}if(prev!=0)prev->suffixLink=p;returnp;}};classLongestCommonSubstring:publicUkkonenSuffixTree{public:LongestCommonSubstring(intfrom,intto):UkkonenSuffixTree(from,to+2){}voidrun(strings1,strings2){createTree(s1+char(size+offset-2)+s2+char(size+offset-1));findLongest(s1,s2);}private:intsllength,position,length;voidfindLongest(strings1,strings2){ booldummy[]={false,false};position=length=0;sllength=s1.length();traverseTree(root,0,0,dummy);if(length==0)cout<<"Strings\""<<s1<<"\"is"<<"\""<<s1<<"\"and\""<<s2<<"\"is"<<"\""<<T.substr(position-length,length)<<"\"oflength"<<length<<endl;}voidtraverseTree(SuffixTreeNode*p,intlt,intlen,bool*whichEdges){booledges[]={false,false};for(chari=0;i<size;i++)if(p->left[i]!=-1){if(p->descendants[i]==0)//ifitisanedgetoif(p->left[i]<=sllength)//aleafcorrespondingwhichEdges[0]=edges[0]=true;//tos1elsewhichEdges[1]=edges[1]=true;//tos2 else{ traverseTree(p->descendants[i],p->left[i], len+(p->right[i]-p->left[i]+1),edges); if(edges[0]) whichEdges[0]=true; if(edges[1]) whichEdges[1]=true; } if(edges[0]&&edges[1]&&len>length){ position=p->left[i]; length=len; } }}};intmain(intargc,stringargv[]){ strings1="abcabc"; strings2="cabaca"; if(argc==3){ s1=argv[1]; s2=argv[2]; } (newLongestCommonSubstring('a','z'))->run(s1,s2);return0;}三、設(shè)計(jì)總結(jié)有了后綴樹，找出字符串Q和R中最長的字符串就很簡單了。首先需要為字符串T=Q$R#創(chuàng)建一個(gè)后綴樹，其中$和#表示沒有在兩個(gè)字符串中使用的字符。在這棵樹中，后綴沒有在內(nèi)部（隱含或顯式）節(jié)點(diǎn)中結(jié)束。對應(yīng)于Q的葉節(jié)點(diǎn)用標(biāo)記包含$（和#）的邊連接其父節(jié)點(diǎn)，對應(yīng)于R的葉節(jié)點(diǎn)用標(biāo)記包含#（但不包含$）的邊連接其父節(jié)點(diǎn)?，F(xiàn)在遍歷樹，查找滿足兩個(gè)條件的節(jié)點(diǎn)。該節(jié)點(diǎn)是一個(gè)子樹的根節(jié)點(diǎn)，其邊標(biāo)記對應(yīng)于兩個(gè)字符串。而且，該節(jié)點(diǎn)應(yīng)對應(yīng)于連接從根節(jié)點(diǎn)到這個(gè)節(jié)點(diǎn)的所有標(biāo)記而得到的最長的字符串。這個(gè)連接的字符串就是為Q和R查找的最長子字符串。在程序清單提供的代碼實(shí)現(xiàn)中，符號$和#是用戶指定的范圍后面的字符，而且自動與兩個(gè)字符串關(guān)聯(lián)。例如，如果范圍是從a到z，且字符串是abccab和daababca，則為字符串T=abccab{daababca|構(gòu)建后綴樹，因?yàn)樵贏SCII字符集中，z的后面是字符“{”和“|“；為了在遍歷樹的過程中確定某個(gè)子樹是否包含對應(yīng)于兩個(gè)字符串的邊（只有指向葉節(jié)點(diǎn)的邊才能提供這類信息），給每個(gè)節(jié)點(diǎn)關(guān)聯(lián)一個(gè)2-單元布爾數(shù)組。當(dāng)檢測到指向葉節(jié)點(diǎn)（葉節(jié)點(diǎn)是隱含節(jié)點(diǎn)）的邊時(shí)，就檢測其標(biāo)記的左索引。如果索引不大于Q的長度，這個(gè)葉節(jié)點(diǎn)就對應(yīng)于Q的一個(gè)后綴，否則，就對應(yīng)于R的一個(gè)后綴。程序維護(hù)共有子字符串的最大長度，在檢測到一個(gè)節(jié)點(diǎn)具有較長的共有子字符串，且其子樹中包含兩個(gè)字符串的后綴時(shí)，就更新最大長度和子字符串結(jié)束的位置。顯然，因?yàn)楹缶Y樹可以在線性時(shí)間內(nèi)創(chuàng)建，樹遍歷也可以在線性時(shí)間內(nèi)完成，所以找出字符串Q和R中最長的共有子字符串就可以在線性時(shí)間O（|O|+|R|）內(nèi)完成。四、收獲