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

課程設計說明書課程名稱：數(shù)據(jù)結構與算法設計題目：最長的共有子字符串院系：計算機科學與信息工程學院設計題目最長的共有子字符串學生姓名所在院系計算機科學與信息工程專業(yè)、年級、班設計要求：設計、實現(xiàn)一個程序，采用后綴樹算法滿足查找兩個字符串中最長的共有子字符串。學生應完成的工作：(1)根據(jù)課程設計要求，分析思路并構建模型，劃分子模塊、完善其功能；(2)根據(jù)各模塊的功能設計并編寫程序段、連接各程序段使之形成一個有機的整體；(3)調試、運行程序進而得到正確的結果；(4)根據(jù)實驗設計運行過程，寫出實驗論文并總結實驗教訓。參考文獻閱讀：(1)C語言程序設計（潭浩強第二版，清華大學出版社）；(2)數(shù)據(jù)結構（吳偉民等C語言版，清華大學出版社）；(3)數(shù)據(jù)結構實驗教程（高曉兵等，清華大學出版社）；(4)算法分析與設計（鄭宗漢、鄭曉明，清華大學出版社）。工作計劃：(1)第一天：小組布置設計題目；說明進度安排。(2)二天：小組審題，查閱資料，進行設計前的必要資料準備。(3)第三天：程序編寫、上機調試(4)第四天：上機調試程序、結果分析。(5)第五天：撰寫設計報告。(6)第六天：設計答辯。任務下達日期：2015年6月任務完成日期：2015年6月指導教師（簽名）：學生（簽名）：目錄一、程序設計…………4二、程序代碼…………6三、設計總結…………15四、收獲致謝…………16五、參考文獻…………17六、附件…………17最長的共有子字符串摘要：查找兩個字符串Q和R中最長的共有子字符串是處理字符串的一個經(jīng)典問題。人們曾一度推測，不可能在線性時間內解決這個問題（Knuth，Morris和Pratt，1977），實際上，使用后綴樹就可以做到。因此，在討論這個問題之前，應先理解并構造后綴樹的Ukkonen算法。關鍵詞：子字符串，共有，后綴樹，索引，節(jié)點。一、程序設計后綴樹中的節(jié)點實現(xiàn)為一個對象，該對象包含子節(jié)點的一個引用數(shù)組；該數(shù)組根據(jù)要處理的文本T來構建，用字母表中的字母進行索引。另外，節(jié)點包含T中字母的右索引和左索引數(shù)組，表示指向子節(jié)點的邊的標記。使用邊的標記和引出該邊的節(jié)點，就可以唯一的標識每條邊，在后綴樹中這是非常重要的，因為后綴樹中的一些節(jié)點可能不是顯式的。為此。使用記號node（顯式節(jié)點，邊的標記）=node（顯式節(jié)點，右，左）。該記號稱為規(guī)范引用，其中使用的顯式節(jié)點在距離使用引用的隱含節(jié)點最近時，稱為規(guī)范節(jié)點。指向葉節(jié)點的邊不需要更新，于是，在UkkonenSuffixTree()中，為了節(jié)省空間，葉節(jié)點也可以省略，只保留指向他們的邊。對于所有字符都不相同的T來說，trie的最壞情況是需要1+（1+2+…+|T|）個節(jié)點，經(jīng)過這樣的處理，trie就變成只有一個根節(jié)點的樹，這是樹的最好情況。邊界路徑的第二部分從第一個非葉節(jié)點開始，經(jīng)過活動點，終止于終點之前的右節(jié)點。后綴樹的處理主要考慮這些節(jié)點。為了給節(jié)點創(chuàng)建一條新邊，如果節(jié)點是隱含的，就必須先把它轉變?yōu)轱@式的。為此，必須分解從節(jié)點的顯式父節(jié)點到節(jié)點本身的邊。為了進行分解，要先找到規(guī)范父節(jié)點。這是findCanonicalNode()函數(shù)的任務。對于implicitNode=node(explicitNode,left,right)，該函數(shù)可以確定explicitNode是否為規(guī)范節(jié)點。如果是，就結束搜索，否則，就查找規(guī)范節(jié)點。要修改樹，應使用函數(shù)update()處理從活動點到終點之間的節(jié)點。testAndSplit()確定當前節(jié)點是否是終點。字母Ti的處理從活動點開始。該活動點很容易確定，因為它是處理完字母Ti-1后得到的終點。為了說明這一點，考慮處理trie中的字母Ti-1。在trie的邊界路徑上，每個節(jié)點都得到了一個可通過Ti-1邊從其父節(jié)點中訪問的新葉節(jié)點。處理過程在已有Ti-1邊的終點處結束。因此，國有新加的葉節(jié)點都在一條包含終點的新邊界路徑上連接起來。這個終點是路徑中的第一個非葉節(jié)點，因此成為開始處理字母Ti之前的活動點，處理過程就從這個活動點開始。在默認情況下，每個節(jié)點都帶有三個包含128個單元的數(shù)組，每個文本字母都是數(shù)組的一個索引。如果已知字符的范圍，范圍中的第一個和最后一個字符就可以作為參數(shù)提供給構造函數(shù)，構造函數(shù)會把變量offset設置為第一個字符，對于每個文本字符，索引可以通過減去變量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;}三、設計總結有了后綴樹，找出字符串Q和R中最長的字符串就很簡單了。首先需要為字符串T=Q$R#創(chuàng)建一個后綴樹，其中$和#表示沒有在兩個字符串中使用的字符。在這棵樹中，后綴沒有在內部（隱含或顯式）節(jié)點中結束。對應于Q的葉節(jié)點用標記包含$（和#）的邊連接其父節(jié)點，對應于R的葉節(jié)點用標記包含#（但不包含$）的邊連接其父節(jié)點?，F(xiàn)在遍歷樹，查找滿足兩個條件的節(jié)點。該節(jié)點是一個子樹的根節(jié)點，其邊標記對應于兩個字符串。而且，該節(jié)點應對應于連接從根節(jié)點到這個節(jié)點的所有標記而得到的最長的字符串。這個連接的字符串就是為Q和R查找的最長子字符串。在程序清單提供的代碼實現(xiàn)中，符號$和#是用戶指定的范圍后面的字符，而且自動與兩個字符串關聯(lián)。例如，如果范圍是從a到z，且字符串是abccab和daababca，則為字符串T=abccab{daababca|構建后綴樹，因為在ASCII字符集中，z的后面是字符“{”和“|“；為了在遍歷樹的過程中確定某個子樹是否包含對應于兩個字符串的邊（只有指向葉節(jié)點的邊才能提供這類信息），給每個節(jié)點關聯(lián)一個2-單元布爾數(shù)組。當檢測到指向葉節(jié)點（葉節(jié)點是隱含節(jié)點）的邊時，就檢測其標記的左索引。如果索引不大于Q的長度，這個葉節(jié)點就對應于Q的一個后綴，否則，就對應于R的一個后綴。程序維護共有子字符串的最大長度，在檢測到一個節(jié)點具有較長的共有子字符串，且其子樹中包含兩個字符串的后綴時，就更新最大長度和子字符串結束的位置。顯然，因為后綴樹可以在線性時間內創(chuàng)建，樹遍歷也可以在線性時間內完成，所以找出字符串Q和R中最長的共有子字符串就可以在線性時間O（|O|+|R|）內完成。四、收獲