posts - 183,  comments - 10,  trackbacks - 0
利用后缀数组求解该问题。
首先用后缀数组拆分字符串,然后对后缀数组排序,在对后缀数组一次遍历,计算相邻的两个字符串,从头开始的最大公共子串。
实现:
 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++ == *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.html
http://blog.csdn.net/baiwen1979/archive/2008/03/24/2212147.aspx
http://ds.fzu.edu.cn/fine/resources/
http://ds.fzu.edu.cn/fine/acm/index.asp
posted on 2011-05-23 18:27 unixfy 阅读(567) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理