生活随笔
收集整理的這篇文章主要介紹了
最长重复子串和最长不重复子串求解
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
最長重復子串和最長不重復子串求解
本文內容框架：
§1 最長重復子串
基本方法、KMP算法求解、后綴數組求解
§2 最長不重復子串
基本方法、動態規劃、動態規劃+Hash
§3 小結
?
§1最長重復子串
?
1.1問題描述
?
首先這是一個單字符串問題。子字符串R 在字符串L 中至少出現兩次，則稱R 是L 的重復子串。重復子串又分為可重疊重復子串和不可重疊重復子串。
?
1.2基本方法
?
枚舉子串，讓子串和子串進行比較。直接看代碼：
╔
C代碼 ? ?????int?maxlen;??????int?maxindex;????void?outputLRS(char?*?arr);?????????int?comlen(char?*?p,?char?*?q)??{??????int?len?=?0;??????while(*p?&&?*q?&&?*p++?==?*q++)??????{??????????++len;??????}??????return?len;??}?????void?LRS_base(char?*?arr,?int?size)??{??????for(int?i?=?0;?i?<?size;?++i)??????{??????????for(int?j?=?i+1;?j?<?size;?++j)??????????{??????????????int?len?=?comlen(&arr[i],&arr[j]);??????????????if(len?>?maxlen)??????????????{??????????????????maxlen?=?len;??????????????????maxindex?=?i;??????????????}??????????}??????}??????outputLRS(arr);??}??
?╝①
優化思路
一般的優化方法就是在充分利用已有的結果，最長重復子串的長度增加一定是建立在之前已經找到的重復子串之上的，充分利用已找到的重復子串的位置和長度是優化的一個重點，此外還有就是未不是重復子串的，以后就不會被包含在重復子串內，如"ab"只有一個，則重復子串就不能包含"ab"（允許重疊的重復子串例外）。
?
1.2KMP算法求解
?
對KMP算法還不是很了解的，可以查看我的另一篇博文（不懂猛點），在KMP算法的關鍵就是求解next數組，針對next[j]=k,可以得到P[0,1,...,k-1]=P[j-k,j-k+1,...,j-1]。看到P[0,1,...,k-1]=P[j-k,j-k+1,...,j-1]應該會眼前一亮，大腦頓時清醒些，這不就是重復子串嗎！由此求解最長重復子串就轉化為求解KMP算法next數組中的最大值（即max{next[j]=k}。
現在就是求解next數組的問題了，還是直接查看代碼：
╔
?
C代碼 ? int?getNext(char?*str,int?*next)??{??????int?len=strlen(str);??????int?index=0;??????int?k=-1;??????next[0]=k;??????int?max=0;??????????????while?(index<len)??????{??????????if?(k==-1?||?str[index]==str[k])??????????{??????????????k++;??????????????index++;??????????????next[index]=k;??????????????if?(k>max)??????????????{??????????????????max=k;??????????????}??????????}??????????else??????????????k=next[k];??????}????????return?max;??}????int?main()??{??????char?str[50];??????cin>>str;??????int?max=0;??????int?nextMax;??????int?index;??????int?maxIndex;??????int?len=strlen(str);????????????for?(index=0;index<len-1;index++)??????{??????????int?*next=new?int[len-index];??????????nextMax=getNext(str+index,next);??????????if?(nextMax>max)??????????{??????????????max=nextMax;??????????????maxIndex=index;??????????}??????}??????????????????cout<<"最長字串：?";??????for?(index=0;index<max;index++)??????{??????????cout<<str[index+maxIndex];??????}??????cout<<endl;????????????return?0;??}??
╝②?
?
1.3后綴數組求解
?
后綴數組在我的另外一篇博文有介紹，還沒有概念的可以移步查看點擊。后綴數組就是保留字符串所有位置到字符串末尾的子字符串，a[i]就是第i位置到末尾的子串。有了后綴數組，對后綴數組進行排序，然后進行求后綴數組相鄰元素的最大前綴就是最大重復子串。
╔
?
Cpp代碼 ? #include?<iostream>???using?namespace?std;???????const?int?MAXN?=?1000;?????int?mycmp(const?void*?p1,?const?void*?p2)???{???????return?strcmp(*(char*?const*)p1,?*(char*?const*)p2);???}??????int?getLen(char*?p,?char*?q)???{???????int?ret?=?0;???????while?(*p?&&?*p++?==?*q++)???????{???????????++ret;???????}???????return?ret;???}??????char*?foo(char?result[],?char?s[])???{???????int?len?=?strlen(s);???????char**?suffix?=?new?char*[len];???????for?(int?i?=?0;?i?<?len;?++i)???????{???????????suffix[i]?=?s?+?i;???????}???????qsort(suffix,?len,?sizeof?(char*),?mycmp);???????????????????????????????????int?maxlen?=?0,?maxi?=?0,?maxj?=?0,?temp?=?0;???????for?(int?i?=?0;?i?<?len?-?1;?++i)???????{???????????temp?=?getLen(suffix[i],?suffix[i?+?1]);???????????if?(temp?>?maxlen)???????????{???????????????maxlen?=?temp;???????????????maxi?=?i;???????????????maxj?=?i?+?1;???????????}???????}???????????????????????????????????for?(int?i?=?0;?i?<?maxlen;?++i)???????{???????????result[i]?=?suffix[maxi][i];???????}???????result[maxlen]?=?'\0';???????return?result;???}??????int?main()???{???????char?s[MAXN];???????char?result[MAXN];???????while?(cin?>>?s)???????{???????????cout?<<?foo(result,?s)?<<?endl;???????}???????return?0;??}??
?
╝③
§2最長不重復子串?
╔
2.1問題描述
?
從一個字符串中找到一個連續子串，該子串中任何兩個字符不能相同，求子串的最大長度并輸出一條最長不重復子串。
下面介紹四種方法逐步優化，時間復雜度從O(n2）到O(n)。
?
2.2基本算法（使用hash)
?
要求子串中的字符不能重復，判重問題首先想到的就是hash，尋找滿足要求的子串，最直接的方法就是遍歷每個字符起始的子串，輔助hash，尋求最長的不重復子串，由于要遍歷每個子串故復雜度為O(n^2)，n為字符串的長度，輔助的空間為常數hash[256]。
?
C代碼 ? ????int?maxlen;??int?maxindex;??void?output(char?*?arr);???????char?visit[256];?????void?LNRS_hash(char?*?arr,?int?size)??{??????int?i,?j;??????for(i?=?0;?i?<?size;?++i)??????{??????????memset(visit,0,sizeof?visit);??????????visit[arr[i]]?=?1;??????????for(j?=?i+1;?j?<?size;?++j)??????????{??????????????if(visit[arr[j]]?==?0)??????????????{??????????????????visit[arr[j]]?=?1;??????????????}else??????????????{??????????????????if(j-i?>?maxlen)??????????????????{??????????????????????maxlen?=?j?-?i;??????????????????????maxindex?=?i;??????????????????}??????????????????break;??????????????}??????????}??????????if((j?==?size)?&&?(j-i?>?maxlen))??????????{??????????????maxlen?=?j?-?i;??????????????maxindex?=?i;??????????}??????}??????output(arr);??}??
?
2.3動態規劃求解
?
動態規劃思想就是用于處理有重疊問題的求解，最大不重復子串一定是兩個相同字符夾著的一段字符串加上這個字符，如abcac這里的最大不重復子串是a夾的一段。
當一個最長子串結束時（即遇到重復的字符），新的子串的長度是與第一個重復的字符的下標有關的，如果該下標在上一個最長子串起始位置之前，則dp[i] = dp[i-1] + 1，即上一個最長子串的起始位置也是當前最長子串的起始位置；如果該下標在上一個最長子串起始位置之后，則新的子串是從該下標之后開始的。簡短幾句話可能講不是很明白，不過好在有程序可以幫助理解，慣例下面附上程序：
C代碼 ? ??int?dp[30];?????void?LNRS_dp(char?*?arr,?int?size)??{??????int?i,?j;??????int?last_start?=?0;???????????maxlen?=?maxindex?=?0;?????????dp[0]?=?1;??????for(i?=?1;?i?<?size;?++i)??????{??????????for(j?=?i-1;?j?>=?last_start;?--j)???????????{??????????????if(arr[j]?==?arr[i])??????????????{??????????????????dp[i]?=?i?-?j;??????????????????last_start?=?j+1;???????????????????break;??????????????}else?if(j?==?last_start)???????????????{??????????????????dp[i]?=?dp[i-1]?+?1;??????????????}??????????}??????????if(dp[i]?>?maxlen)??????????{??????????????maxlen?=?dp[i];??????????????maxindex?=?i?+?1?-?maxlen;??????????}??????}??????output(arr);??}??
2.4動態規劃+Hash求解
上面動態規劃求解時間復雜度還是O(n2)，主要是還是進行“回頭”查找了重復元素位置，其實，上面并不是真正的動態規劃方法，因為上面的求解過程沒有記錄有用的結果，所以可以通過記錄之前出現的下標來改進算法，這樣就不用每次都回去查找重復元素位置，這其實才是真正的動態規劃方法，只是記錄結果是用的Hash，這樣的時間復雜度就是O(n)。
?
C代碼 ? ??void?LNRS_dp_hash(char?*?arr,?int?size)??{??????memset(visit,?-1,?sizeof?visit);??????memset(dp,?0,?sizeof?dp);??????maxlen?=?maxindex?=?0;??????dp[0]?=?1;??????visit[arr[0]]?=?0;??????int?last_start?=?0;?????????for(int?i?=?1;?i?<?size;?++i)??????{??????????if(visit[arr[i]]?==?-1)??????????{??????????????dp[i]?=?dp[i-1]?+?1;??????????????visit[arr[i]]?=?i;???????????}else??????????{??????????????if(last_start?<=?visit[arr[i]])??????????????{??????????????????dp[i]?=?i?-?visit[arr[i]];??????????????????last_start?=?visit[arr[i]]?+?1;??????????????????visit[arr[i]]?=?i;???????????????}else??????????????{??????????????????dp[i]?=?dp[i-1]?+?1;??????????????}?????????????}??????????if(dp[i]?>?maxlen)??????????{??????????????maxlen?=?dp[i];??????????????maxindex?=?i?+?1?-?maxlen;??????????}??????}??????output(arr);??}??
?
?進一步優化
上面的程序因為輔助的空間多了，是不是還能優化，仔細看DP最優子問題解的更新方程：
dp[i] = dp[i-1] + 1;
dp[i-1]不就是更新dp[i]當前的最優解么？這與最大子數組和問題的優化幾乎同出一轍，我們不需要O(n)的輔助空間去存儲子問題的最優解，而只需O(1)的空間就可以了，至此，我們找到了時間復雜度O(N)，輔助空間為O(1)（一個額外變量與256大小的散列表）的算法，代碼如下：
注意：當前最長子串的構成是與上一次最長子串相關的，故要記錄上一次最長子串的起始位置！
?
C代碼 ? ??void?LNRS_dp_hash_impro(char?*?arr,?int?size)??{??????memset(visit,?-1,?sizeof?visit);??????maxlen?=?maxindex?=?0;??????visit[arr[0]]?=?0;??????int?curlen?=?1;??????int?last_start?=?0;?????????for(int?i?=?1;?i?<?size;?++i)??????{??????????if(visit[arr[i]]?==?-1)??????????{??????????????++curlen;??????????????visit[arr[i]]?=?i;???????????}else??????????{??????????????if(last_start?<=?visit[arr[i]])??????????????{??????????????????curlen?=?i?-?visit[arr[i]];??????????????????last_start?=?visit[arr[i]]?+?1;??????????????????visit[arr[i]]?=?i;???????????????}else??????????????{??????????????????++curlen;??????????????}??????????}??????????if(curlen?>?maxlen)??????????{??????????????maxlen?=?curlen;??????????????maxindex?=?i?+?1?-?maxlen;??????????}??????}??????output(arr);??}??
?
?最后在給出測試用例
?
C代碼 ? ??void?output(char?*?arr)??{??????if(maxlen?==?0)??????{??????????printf("NO?LNRS\n");??????}??????printf("The?len?of?LNRS?is?%d\n",maxlen);?????????int?i?=?maxindex;??????while(maxlen--)??????{??????????printf("%c",arr[i++]);??????}??????printf("\n");??}?????void?main()??{???????char?arr[]?=?"abcaacdeabacdefg";?????????????????LNRS_hash(arr,strlen(arr));?????????????????LNRS_dp(arr,strlen(arr));?????????????????LNRS_dp_hash(arr,strlen(arr));?????????????????LNRS_dp_hash_impro(arr,strlen(arr));??}??
?╝④
?
§3 小結
這篇文章把字符串最長重復子串和最長不重復子串的求解方法，能有了一定的認識和理解，基本可以掌握這些方法。如果你有任何建議或者批評和補充，請留言指出，不勝感激，更多參考請移步互聯網。
?
?
參考：
①勇幸|Thinking： http://www.ahathinking.com/archives/121.html
②huang12315： http://blog.csdn.net/huang12315/article/details/6455090
③unixfy： http://www.cppblog.com/unixfy/archive/2011/05/23/146986.html
④勇幸|Thinking： http://www.ahathinking.com/archives/123.html
?
總結
以上是生活随笔為你收集整理的最长重复子串和最长不重复子串求解的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
