Advertisement
Dang_Quan_10_Tin

XÂU ĐỐI ĐỐI XỨNG

Aug 15th, 2022
508
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.58 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using ll = long long;
  5.  
  6. constexpr int N = 3e5 + 5;
  7. constexpr ll base = 37;
  8. constexpr ll mod = 1e9 + 3;
  9.  
  10. // Fenwick Tree để tính tổng nhanh
  11. struct FenwickTree
  12. {
  13.     int a[N], n;
  14.     FenwickTree()
  15.     {
  16.         memset(a, 0, sizeof a);
  17.     }
  18.  
  19.     void Update(int p, int v)
  20.     {
  21.         for (; p <= n; p += p & -p)
  22.             a[p] += v;
  23.     }
  24.  
  25.     int Get(int p)
  26.     {
  27.         int ans(0);
  28.         for (; p; p -= p & -p)
  29.             ans += a[p];
  30.         return ans;
  31.     }
  32.  
  33.     int Get(int l, int r)
  34.     {
  35.         return Get(r) - Get(l - 1);
  36.     }
  37. } f;
  38.  
  39. int n, l[N], ans(0), piv(0);
  40. string s;
  41. ll has[N], rhas[N], Pow[N];
  42.  
  43. // Chuẩn bị cho quá trình hash
  44. void HASH(string s)
  45. {
  46.     Pow[0] = 1;
  47.     for (int i = 1; i <= n; ++i)
  48.     {
  49.         has[i] = (has[i - 1] * base + s[i] - 'a' + 1) % mod;                       // Hash xuôi
  50.         rhas[n - i + 1] = (rhas[n - i + 2] * base + s[n - i + 1] - 'a' + 1) % mod; // Hash ngược
  51.         Pow[i] = Pow[i - 1] * base % mod;
  52.     }
  53. }
  54.  
  55. void Read()
  56. {
  57.     cin >> s;
  58.     n = s.size();
  59.     f.n = n;
  60.     s = " " + s;
  61.     HASH(s);
  62. }
  63.  
  64. // Get hash xuôi
  65. ll Get(int x, int y)
  66. {
  67.     return ((has[y] - has[x - 1] * Pow[y - x + 1]) % mod + mod) % mod;
  68. }
  69.  
  70. // Get hash ngược
  71. ll rGet(int x, int y)
  72. {
  73.     return ((rhas[x] - rhas[y + 1] * Pow[y - x + 1]) % mod + mod) % mod;
  74. }
  75.  
  76. void Solve()
  77. {
  78.     // *Tính l_i = Bán kính palindrome tâm (i, i+1)
  79.     for (int i = 1; i < n; ++i)
  80.     {
  81.         // low, mid, high
  82.         int le = 0, minh, hoang = n;
  83.  
  84.         while (le <= hoang)
  85.         {
  86.             minh = (le + hoang) / 2;
  87.             if (minh <= i && minh <= n - i && Get(i - minh + 1, i + minh) == rGet(i - minh + 1, i + minh))
  88.                 le = minh + 1;
  89.             else
  90.                 hoang = minh - 1;
  91.         }
  92.  
  93.         l[i] = hoang;
  94.     }
  95.  
  96.     // Như anh đã nói hôm trước, điều kiện để thằng j có thể là tâm của palindrome bên phải của palindpalindrome tâm i là:
  97.     /*
  98.         i < j <= i + l_i
  99.         l_j >= j - i
  100.         j - i <= i + l_i - j
  101.     */
  102.     /*
  103.         - i < j <= (i * 2 + l_i) / 2
  104.         - j - l_j <= i
  105.     */
  106.  
  107.     // Nếu anh thêm các "tâm" vào theo thứ tự (j-l[j]) tăng dần, anh sẽ bỏ được điều kiện 2; chỉ cần kiểm tra điều kiện 1
  108.     vector<int> b;
  109.     b.reserve(n);
  110.  
  111.     for (int i = 1; i < n; ++i)
  112.         if (l[i] > 0)
  113.             b.emplace_back(i);
  114.  
  115.     sort(b.begin(), b.end(), [&](const int &x, const int &y)
  116.          { return x - l[x] < y - l[y]; });
  117.  
  118.     for (int i = 1, j = 0; i < n; ++i)
  119.         if (l[i] > 0)
  120.         {
  121.             while (j < (int)b.size() && b[j] - l[b[j]] <= i)
  122.             {
  123.                 f.Update(b[j], 1);
  124.                 ++j;
  125.             }
  126.  
  127.             // low, mid, high
  128.             int lee = i, Min, ho = (i * 2 + l[i]) / 2;
  129.             int sum = f.Get(i + 1, ho);
  130.  
  131.             while (lee <= ho)
  132.             {
  133.                 Min = (lee + ho) / 2;
  134.                 if (f.Get(i + 1, Min) < sum)
  135.                     lee = Min + 1;
  136.                 else
  137.                     ho = Min - 1;
  138.             }
  139.  
  140.             if (ans < (lee - i) * 4)
  141.             {
  142.                 ans = (lee - i) * 4;
  143.                 piv = i;
  144.             }
  145.         }
  146.  
  147.     if (ans == 0)
  148.         cout << "-1";
  149.     else
  150.         cout << s.substr(piv - ans / 2 + 1, ans);
  151.  
  152.     cerr << "\n"
  153.          << ans << " " << piv;
  154. }
  155.  
  156. int32_t main()
  157. {
  158.     ios::sync_with_stdio(0);
  159.     cin.tie(0);
  160.     cout.tie(0);
  161.     Read();
  162.     Solve();
  163. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement