• API
• FAQ
• Tools
• Archive
SHARE
TWEET # Global Round 7, solution of the problem D isaf27  Mar 19th, 2020 5,562 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <bits/stdc++.h>
2.
3. using namespace std;
4.
5. const int M = (int)(2e6 + 239);
6.
7. int pref[M], c;
8.
9. string solve_palindrome(const string& s)
10. {
11.     string a = s;
12.     reverse(a.begin(), a.end());
13.     a = s + "#" + a;
14.     c = 0;
15.     for (int i = 1; i < (int)a.size(); i++)
16.     {
17.         while (c != 0 && a[c] != a[i])
18.             c = pref[c - 1];
19.         if (a[c] == a[i])
20.             c++;
21.         pref[i] = c;
22.     }
23.     return s.substr(0, c);
24. }
25.
26. void solve()
27. {
28.     string t;
29.     cin >> t;
30.     int l = 0;
31.     while (l < (int)t.size() - l - 1)
32.     {
33.         if (t[l] != t[(int)t.size() - l - 1])
34.             break;
35.         l++;
36.     }
37.     if (l > 0)
38.         cout << t.substr(0, l);
39.     if ((int)t.size() > 2 * l)
40.     {
41.         string s = t.substr(l, (int)t.size() - 2 * l);
42.         string a = solve_palindrome(s);
43.         reverse(s.begin(), s.end());
44.         string b = solve_palindrome(s);
45.         if ((int)a.size() < (int)b.size())
46.             swap(a, b);
47.         cout << a;
48.     }
49.     if (l > 0)
50.         cout << t.substr((int)t.size() - l, l);
51.     cout << "\n";
52. }
53.
54. int main()
55. {
56.     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
57.     int t;
58.     cin >> t;
59.     while (t--)
60.         solve();
61.     return 0;
62. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.
Top