找出字符串中最大的子串
子串：當重復出現某個字符時，這個字符串就是子串
例如：
字符串 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 閱讀(643)
評論(0) 編輯 收藏 引用