連續(xù)遞增最長(zhǎng)子串，其做法與最大連續(xù)子串差不多。逐個(gè)掃描，記錄最長(zhǎng)子串的長(zhǎng)度和邊界。
這里的遞增有兩種方式，一是只要后一個(gè)元素比前一個(gè)元素大于或等于即可。
第二種方式是，后一個(gè)元素必須比前一個(gè)元素大于 1。
1 #include <iostream>
2 #include <string>
3 using namespace std;
4
5 // 后一個(gè)元素大于或等于前一個(gè)元素
6 int foo(const string& s, size_t& l, size_t& r)
7 {
8 int ret = 1, now = 1;
9 size_t l2, r2;
10 l2 = r2 = 0;
11 l = r = l2;
12 for (size_t i = 1; i < s.size(); ++i)
13 {
14 if (s[i] >= s[i - 1])
15 {
16 ++now;
17 ++r2;
18 }
19 else
20 {
21 now = 1;
22 l2 = r2 = i;
23 }
24 if (now > ret)
25 {
26 ret = now;
27 l = l2;
28 r = r2;
29 }
30 }
31 return ret;
32 }
33
34 // 后一個(gè)元素必須比前一個(gè)元素大于 1
35 int bar(const string& s, size_t& l, size_t& r)
36 {
37 int ret = 1, now = 1;
38 size_t l2, r2;
39 l2 = r2 = 0;
40 l = r = l2;
41 for (size_t i = 1; i < s.size(); ++i)
42 {
43 if (s[i] - s[i - 1] == 1)
44 {
45 ++now;
46 ++r2;
47 }
48 else
49 {
50 now = 1;
51 l2 = r2 = i;
52 }
53 if (now > ret)
54 {
55 ret = now;
56 l = l2;
57 r = r2;
58 }
59 }
60 return ret;
61 }
62
63 int main()
64 {
65 string s;
66 while (cin >> s)
67 {
68 size_t l, u;
69 int len = foo(s, l, u);
70 cout << len << endl;
71 while (l <= u)
72 {
73 cout << s[l++] << ' ';
74 }
75 cout << endl;
76
77 len = bar(s, l, u);
78 cout << len << endl;
79 while (l <= u)
80 {
81 cout << s[l++] << ' ';
82 }
83 cout << endl;
84 }
85 return 0;
86 }
posted on 2011-05-21 10:35
unixfy 閱讀(427)
評(píng)論(0) 編輯 收藏 引用