問題描述
給定一個字符串，求出其最長重復子串
例如：abcdabcd
最長重復子串是 abcd，最長重復子串可以重疊
例如：abcdabcda，這時最長重復子串是 abcda，中間的 a 是被重疊的。

直觀的解法是，首先檢測長度為 n - 1 的字符串情況，如果不存在重復則檢測 n - 2, 一直遞減下去，直到 1 。
這種方法的時間復雜度是 O(N * N * N)，其中包括三部分，長度緯度、根據長度檢測的字符串數目、字符串檢測。

改進的方法是利用后綴數組
后綴數組是一種數據結構，對一個字符串生成相應的后綴數組后，然后再排序，排完序依次檢測相鄰的兩個字符串的開頭公共部分。
這樣的時間復雜度為：生成后綴數組 O(N)，排序 O(NlogN*N) 最后面的 N 是因為字符串比較也是 O(N)
依次檢測相鄰的兩個字符串 O(N * N)，總的時間復雜度是 O(N^2*logN)，優于第一種方法的 O(N^3)


????? 對于類似從給定的文本中，查找其中最長的重復子字符串的問題，可以采用“后綴數組”來高效地完成此任務。后綴數組使用文本本身和n個附加指針（與文本數組相應的指針數組）來表示輸入文本中的n個字符的每個子字符串。
??? 首先，如果輸入字符串存儲在c[0..n-1]中，那么就可以使用類似于下面的代碼比較每對子字符串：
int main(void) {int i , j , thislen , maxlen = -1;..................for(i = 0 ; i < n ; ++i ){for(j = i+1 ; j < n ; ++j ){if((thislen = comlen(&c[i] , &c[j])) > maxlen){maxlen = thislen;maxi = i;maxj = j;}}}..................return 0; }當作為comlen函數參數的兩個字符串長度相等時，該函數便返回這個長度值，從第一個字符開始：
int comlen( char *p, char *q ) {int i = 0;while( *p && (*p++ == *q++) )++i;return i; }??? 由于該算法查看所有的字符串對，所以它的時間和n的平方成正比。下面便是使用“后綴數組”的解決辦法。
??? 如果程序至多可以處理MAXN個字符，這些字符被存儲在數組c中：
#define MAXCHAR 5000 //最長處理5000個字符char c[MAXCHAR], *a[MAXCHAR];在讀取輸入時，首先初始化a，這樣，每個元素就都指向輸入字符串中的相應字符：
n = 0; while( (ch=getchar())!='\n' ) {a[n] = &c[n];c[n++] = ch; } c[n]='\0'; // 將數組c中的最后一個元素設為空字符，以終止所有字符串這樣，元素a[0]指向整個字符串，下一個元素指向以第二個字符開始的數組的后綴，等等。如若輸入字符串為"banana",該數組將表示這些后綴：
a[0]:banana
a[1]:anana
a[2]:nana
a[3]:ana
a[4]:na
a[5]:a
由于數組a中的指針分別指向字符串中的每個后綴，所以將數組a命名為"后綴數組"

第二、對后綴數組進行快速排序，以將后綴相近的（變位詞）子串集中在一起
qsort(a, n, sizeof(char*), pstrcmp)后
a[0]:a
a[1]:ana
a[2]:anana
a[3]:banana
a[4]:na
a[5]:nana
第三、使用以下comlen函數對數組進行掃描比較鄰接元素，以找出最長重復的字符串：
for(i = 0 ; i < n-1 ; ++i ) {temp=comlen( a[i], a[i+1] );if( temp>maxlen ){maxlen=temp;maxi=i;} } printf("%.*s\n",maxlen, a[maxi]);完整的實現代碼如下：
#include <iostream> using namespace std;#define MAXCHAR 5000 //最長處理5000個字符char c[MAXCHAR], *a[MAXCHAR];int comlen( char *p, char *q ) {int i = 0;while( *p && (*p++ == *q++) )++i;return i; }int pstrcmp( const void *p1, const void *p2 ) {return strcmp( *(char* const *)p1, *(char* const*)p2 ); }int main(void) {char ch;int n=0;int i, temp;int maxlen=0, maxi=0;printf("Please input your string:\n");n = 0;while( (ch=getchar())!='\n' ){a[n] = &c[n];c[n++] = ch;}c[n]='\0'; // 將數組c中的最后一個元素設為空字符，以終止所有字符串qsort( a, n, sizeof(char*), pstrcmp );for(i = 0 ; i < n-1 ; ++i ){temp=comlen( a[i], a[i+1] );if( temp>maxlen ){maxlen=temp;maxi=i;}}printf("%.*s\n",maxlen, a[maxi]);return 0; } 方法二：KMP
通過使用next數組的特性，同樣可以求最長重復子串，不過時間復雜度有點高挖。。
#include<iostream> using namespace std;const int MAX = 100000; int next[MAX]; char str[MAX];void GetNext(char *t) {int len = strlen(t);next[0] = -1;int i = 0 , j = -1;while(i < len){if(j == -1 || t[i] == t[j]){i++;j++;if(t[i] != t[j])next[i] = j;elsenext[i] = next[j];}elsej = next[j];} } int main(void) {int i , j , index , len;cout<<"Please input your string:"<<endl;cin>>str;char *s = str;len = 0;for(i = 0 ; *s != '\0' ; s++ , ++i){GetNext(s);for(j = 1 ; j <= strlen(s) ; ++j){if(next[j] > len){len = next[j];index = i + j; //index是第一個最長重復串在str中的位置 }}}if(len > 0){for(i = index - len ; i < index ; ++i)cout<<str[i];cout<<endl;}elsecout<<"none"<<endl;return 0; }
題目描述：求最長不重復子串，如abcdefgegcsgcasse，最長不重復子串為abcdefg，長度為7
#include <iostream> #include <list> using namespace std;//思路：用一個數組保存字符出現的次數。用i和j進行遍歷整個字符串。 //當某個字符沒有出現過，次數+1；出現字符已經出現過，次數+1，找到這個字符前面出現的位置的下一個位置，設為i //并將之前的那些字符次數都-1。繼續遍歷，直到'\0' int find(char str[],char *output) {int i = 0 , j = 0;int cnt[26] = {0};int res = 0 , temp = 0;char *out = output;int final;while(str[j] != '\0'){if(cnt[str[j]-'a'] == 0){cnt[str[j]-'a']++;}else{cnt[str[j]-'a']++;while(str[i] != str[j]){ cnt[str[i]-'a']--;i++;}cnt[str[i]-'a']--;i++;} j++;temp = j-i;if(temp > res){res = temp;final = i;}}//結果保存在output里面for(i = 0 ; i < res ; ++i)*out++ = str[final++];*out = '\0';return res; } int main(void) {char a[] = "abcdefg";char b[100];int max = find(a,b);cout<<b<<endl;cout<<max<<endl;return 0; }




與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的后缀数组求最长重复子串的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。