找出字符串中最大的子串
子串：当重复出现某个字符时，这个字符串就是子串
例如：
字符串 abcd13agbf
子串为：abcd13a, bcd13agb
求解 1
两重遍历字符串，检测左右两个端点的字符是否一样，如果相等，则是子串
这种方法直观，时间复杂度为 O(N ^ 2)。
求解 2
尽可能从问题中挖掘潜在的信息，获得的信息越多越有利于解决问题，也就越有可能获得高效的解法。
针对字符，我们知道其 ASCII 范围是 0 - 255 ，我们这设计一个二维数组
int x[256][100];
x 存储每个字符所在的位置
用 int n[256]; 记录每个字符出现的次数
扫描一遍字符串，即可得到我们想要的信息并存储于 x 和 n 中
然后对 x 进行扫描，即可得到最大的子串
第一次扫描字符串时间复杂度是 O(N)
第二次扫描 x ，时间复杂度也是 O(N)
总的时间复杂度为 O(N)
实现：
1 #include <iostream>
2 using namespace std;
3
4 char* maxSubStr(char* s, const char* str)
5 {
6 int left = 0, right = 0;
7 int max = 0;
8 for (int i = 0; i < strlen(str); ++i)
9 {
10 int temp = 1;
11 for (int j = i + 1; j < strlen(str); ++j)
12 {
13 if (str[i] == str[j])
14 {
15 ++temp;
16 if (temp > max)
17 {
18 max = temp;
19 left = i;
20 right = j;
21 }
22 }
23 else
24 {
25 ++temp;
26 }
27 }
28 }
29 int j = 0;
30 for (int i = left; i <= right; ++i, ++j)
31 {
32 s[j] = str[i];
33 }
34 s[j] = '\0';
35 return s;
36 }
37
38 char* maxSubStrX(char* s, const char* str)
39 {
40 static int x[256][100];
41 static int n[256];
42 memset(x, -1, sizeof (x));
43 memset(n, 0, sizeof (n));
44 for (int i = 0; i < strlen(str); ++i)
45 {
46 x[ str[i] ][ n[ str[i] ] ] = i;
47 ++n[str[i]];
48 }
49 int left = 0, right = 0;
50 int max = 0;
51 for (int i = 0; i < 256; ++i)
52 {
53 for (int j = 0; j < n[i] - 1; ++i)
54 {
55 if (x[i][j + 1] - x[i][j] > max)
56 {
57 max = x[i][j + 1] - x[i][j];
58 left = x[i][j];
59 right = x[i][j + 1];
60 }
61 }
62 }
63 int j = 0;
64 for (int i = left; i <= right; ++i, ++j)
65 {
66 s[j] = str[i];
67 }
68 s[j] = '\0';
69 return s;
70 }
71
72 int main()
73 {
74 char str[100], s[100];
75 while (cin >> str)
76 {
77 cout << maxSubStr(s, str) << endl;
78 cout << maxSubStrX(s, str) << endl;
79 }
80 return 0;
81 }
posted on 2011-06-27 18:29
unixfy 阅读(588)
评论(0) 编辑 收藏 引用