hihoCoder #1032 最长回文子串

 1 #include <iostream>
 2 #include <string>
 3 #include <vector>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 
 8 void even_to_odd(string &init) {
 9     init.insert(init.begin(),‘(‘);
10     for (auto i = init.begin() + 1; i != init.end(); i += 2)
11         i = init.insert(i, ‘*‘);
12     init.insert(init.end(),‘*‘);
13     init.insert(init.end(),‘)‘);
14 }
15 void even_to_odd_2(const string &init, string &copy) {
16     copy = string(init.size() * 2 + 3, ‘ ‘);
17     copy[0] = ‘(‘;
18     for (auto i = 0; i < init.size(); i++) {
19         copy[(i + 1) * 2] = init[i];
20         copy[(i + 1) * 2 - 1] = ‘*‘;
21     }
22     copy[copy.size() - 2] = ‘*‘;
23     copy[copy.size() - 1] = ‘)‘;
24 }
25 
26 void compute_symmetry_length(const string &source, vector<int> &record) {
27     for (int cur = 2, pos = 1, right = 1; cur < record.size(); cur++) {
28         record[cur] = max(min(record[2 * pos - cur], record[pos] - cur + pos), record[cur]);
29         for (; source[cur - record[cur] - 1] == source[cur + record[cur] + 1]; record[cur]++) {}
30         if (cur + record[cur] >= right) {
31             right = cur + record[cur];
32             pos = cur;
33         }
34     }
35 }
36 int print_length(const vector<int> &record) {
37     int i = 1;
38     for (size_t p = 0; p < record.size(); p++)
39         i = max(i, record[p]);
40     return i;
41 }
42 int main() {
43     int test_count;
44     cin >> test_count;
45     string init_str, odd_str;
46     for (int i = 0; i < test_count; i++) {
47         cin >> init_str;
48         even_to_odd_2(init_str, odd_str);
49         vector<int> cent_symmetry(odd_str.size(), 0);
50         compute_symmetry_length(odd_str, cent_symmetry);
51         cout << print_length(cent_symmetry) << endl;
52     }
53     return 0;
54 }