求字符串中包含所有字符的最小全集子串
http://www.vanjor.org/blog/2011/05/find-dic-substring/
這其實也是一個最短文摘生成方法
實現方式是：用兩個 left 和 right 指針順序掃描母字符串。
時間復雜度：O(N)
實現：
1 #include <iostream>
2 #include <string>
3 #include <map>
4 #include <cstring>
5 using namespace std;
6
7 string foo(const string& s, const string& t)
8 {
9 int tmap[256], ts[256];
10 memset(tmap, 0, sizeof (tmap));
11 memset(ts, 0, sizeof (ts));
12 int tSize = 0;
13 for (string::size_type i = 0; i != t.size(); ++i)
14 {
15 if (tmap[t[i]] == 0)
16 {
17 tmap[t[i]] = 1;
18 ++tSize;
19 }
20 }
21 string::size_type left = 0, right = s.size() - 1, i = 0, j = 0;
22 int count = 0;
23 while (i < s.size() && tmap[s[i]] == 0)
24 {
25 ++i;
26 }
27 if (i >= s.size())
28 {
29 return string("Not found!");
30 }
31 bool find = false;
32 for (j = i; j < s.size(); ++j)
33 {
34 if (tmap[s[j]] == 1)
35 {
36 ++ts[s[j]];
37 if (ts[s[j]] == 1)
38 {
39 ++count;
40 if (count == tSize)
41 {
42 find = true;
43 if (j - i < right - left)
44 {
45 left = i;
46 right = j;
47 }
48 while (i < s.size())
49 {
50 if (tmap[s[i]] == 1)
51 {
52 --ts[s[i]];
53 if (ts[s[i]] == 0)
54 {
55 --count;
56 if (j - i < right - left)
57 {
58 left = i;
59 right = j;
60 }
61 ++i;
62 break;
63 }
64 }
65 ++i;
66 }
67 while (i < s.size() && tmap[s[i]] == 0)
68 {
69 ++i;
70 }
71 if (i >= s.size())
72 {
73 if (find)
74 {
75 return s.substr(left, right - left + 1);
76 }
77 else
78 {
79 return string("Not found!");
80 }
81 }
82 }
83 }
84 }
85 }
86 if (find)
87 {
88 return s.substr(left, right - left + 1);
89 }
90 else
91 {
92 return string("Not found!");
93 }
94 }
95
96 int main()
97 {
98 string s, t;
99 while (cin >> s >> t)
100 {
101 cout << foo(s, t) << endl;
102 }
103
104 return 0;
105 }
===
http://www.vanjor.org/blog/2011/05/sorting-collections/http://www.vanjor.org/blog/2011/05/find-dic-substring/http://coolshell.cn/articles/3933.htmlhttp://coolshell.cn/http://jsdo.it/norahiko/oxIy/fullscreenhttp://jsdo.it/
posted on 2011-12-28 23:12
unixfy 閱讀(641)
評論(0) 編輯 收藏 引用