最長(zhǎng)重復(fù)子串
問(wèn)題描述
給定一個(gè)字符串，求出其最長(zhǎng)重復(fù)子串
例如 abcdabcd
最長(zhǎng)重復(fù)子串是 abcd
最長(zhǎng)重復(fù)子串可以重疊
例如
abcdabcda
這時(shí)最長(zhǎng)重復(fù)子串是 abcda
中間的 a 是被重疊的。
直觀的解法是，首先檢測(cè)長(zhǎng)度為 n - 1 的字符串情況，如果不存在重復(fù)則檢測(cè) n - 2, 一直遞減下去，直到 1 。
這種方法的時(shí)間復(fù)雜度是 O(N * N * N)，其中包括三部分，長(zhǎng)度緯度、根據(jù)長(zhǎng)度檢測(cè)的字符串?dāng)?shù)目、字符串檢測(cè)。
改進(jìn)的方法是利用后綴數(shù)組
后綴數(shù)組是一種數(shù)據(jù)結(jié)構(gòu)，對(duì)一個(gè)字符串生成相應(yīng)的后綴數(shù)組后，然后再排序，排完序依次檢測(cè)相鄰的兩個(gè)字符串的開(kāi)頭公共部分。
這樣的時(shí)間復(fù)雜度為：
生成后綴數(shù)組 O(N)
排序 O(NlogN*N) 最后面的 N 是因?yàn)樽址容^也是 O(N)
依次檢測(cè)相鄰的兩個(gè)字符串 O(N * N)
總的時(shí)間復(fù)雜度是 O(N^2*logN), 由于第一種方法的 O(N^3)
后綴數(shù)組的實(shí)現(xiàn)：
代碼摘自 CSDN 論壇
http://topic.csdn.net/u/20071002/22/896b1597-fc39-466e-85d3-5bef6f7442f6.html
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4
5 #define MAXCHAR 5000 //最長(zhǎng)處理5000個(gè)字符
6
7 char c[MAXCHAR], *a[MAXCHAR];
8
9 int comlen( char *p, char *q ){
10 int i = 0;
11 while( *p && (*p++ == *q++) )
12 ++i;
13 return i;
14 }
15
16 int pstrcmp( const void *p1, const void *p2 ){
17 return strcmp( *(char* const *)p1, *(char* const*)p2 );
18 }
19
20 int main( ){
21 char ch;
22 int n=0;
23 int i, temp;
24 int maxlen=0, maxi=0;
25 printf("Please input your string:\n");
26 while( (ch=getchar())!='\n' ){
27 a[n]=&c[n];
28 c[n++]=ch;
29 }
30 c[n]='\0';
31 qsort( a, n, sizeof(char*), pstrcmp );
32 for(i=0; i<n-1; ++i ){
33 temp=comlen( a[i], a[i+1] );
34 if( temp>maxlen ){
35 maxlen=temp;
36 maxi=i;
37 }
38 }
39 printf("%.*s\n",maxlen, a[maxi]);
40 system("PAUSE");
41 return 0;
42 }
參考：
http://topic.csdn.net/u/20071002/22/896b1597-fc39-466e-85d3-5bef6f7442f6.htmlhttp://blog.csdn.net/kongming_acm/article/details/6232439http://blog.sina.com.cn/s/blog_5133d4dd0100a4qd.htmlhttp://www.programbbs.com/bbs/view35-20014-1.htmhttp://hi.baidu.com/fangm/blog/item/58fd1a4c20a5eafdd72afcd0.htmlhttp://www.cnblogs.com/dyh333/articles/1801714.htmlhttp://www.byvoid.com/blog/tag/%E6%9C%80%E9%95%BF%E9%87%8D%E5%A4%8D%E5%AD%90%E4%B8%B2/http://www.shnenglu.com/Joe/archive/2011/08/19/153851.html
posted on 2011-09-13 16:01
unixfy 閱讀(7838)
評(píng)論(0) 編輯 收藏 引用