利用后綴數(shù)組求解該問題。
首先用后綴數(shù)組拆分字符串，然后對后綴數(shù)組排序，在對后綴數(shù)組一次遍歷，計算相鄰的兩個字符串，從頭開始的最大公共子串。
實現(xiàn)：
1 #include <iostream>
2 using namespace std;
3
4 const int MAXN = 1000;
5
6 int mycmp(const void* p1, const void* p2)
7 {
8 return strcmp(*(char* const*)p1, *(char* const*)p2);
9 }
10
11 int getLen(char* p, char* q)
12 {
13 int ret = 0;
14 while (*p && *p++ == *q++)
15 {
16 ++ret;
17 }
18 return ret;
19 }
20
21 char* foo(char result[], char s[])
22 {
23 int len = strlen(s);
24 char** suffix = new char*[len];
25 for (int i = 0; i < len; ++i)
26 {
27 suffix[i] = s + i;
28 }
29 qsort(suffix, len, sizeof (char*), mycmp);
30 //for (int i = 0; i < len; ++i)
31 //{
32 // cout << suffix[i] << endl;
33 //}
34 int maxlen = 0, maxi = 0, maxj = 0, temp = 0;
35 for (int i = 0; i < len - 1; ++i)
36 {
37 temp = getLen(suffix[i], suffix[i + 1]);
38 if (temp > maxlen)
39 {
40 maxlen = temp;
41 maxi = i;
42 maxj = i + 1;
43 }
44 }
45 //cout << maxlen << endl;
46 //cout << suffix[maxi] << endl;
47 //cout << suffix[maxj] << endl;
48 //printf("%.*s\n", maxlen, suffix[maxi]);
49 for (int i = 0; i < maxlen; ++i)
50 {
51 result[i] = suffix[maxi][i];
52 }
53 result[maxlen] = '\0';
54 return result;
55 }
56
57 int main()
58 {
59 char s[MAXN];
60 char result[MAXN];
61 while (cin >> s)
62 {
63 cout << foo(result, s) << endl;
64 }
65 return 0;
66 }
http://hi.baidu.com/prettydidy/blog/item/84bf6a37afd3ef1c90ef399f.htmlhttp://blog.csdn.net/baiwen1979/archive/2008/03/24/2212147.aspxhttp://ds.fzu.edu.cn/fine/resources/http://ds.fzu.edu.cn/fine/acm/index.asp
posted on 2011-05-23 18:27
unixfy 閱讀(590)
評論(0) 編輯 收藏 引用