Untitled
unknown
plain_text
a month ago
2.8 kB
4
Indexable
Never
#include <bits/stdc++.h> using namespace std; #define ll long long #define all(x) (x).begin(), (x).end() #define f(i, n) for (int i = 0; i < n; i++) #define trace(x) cerr << #x << ": " << x << '\n' string s, r; const int N = 1e3 + 9; int n; int power(long long n, long long k, const int mod) { int ans = 1 % mod; n %= mod; if (n < 0) n += mod; while (k) { if (k & 1) ans = (long long)ans * n % mod; n = (long long)n * n % mod; k >>= 1; } return ans; } const int MOD1 = 127657753, MOD2 = 987654319; const int p1 = 137, p2 = 277; int ip1, ip2; pair<int, int> pw[N], ipw[N]; void prec() { pw[0] = {1, 1}; for (int i = 1; i < N; i++) { pw[i].first = 1LL * pw[i - 1].first * p1 % MOD1; pw[i].second = 1LL * pw[i - 1].second * p2 % MOD2; } ip1 = power(p1, MOD1 - 2, MOD1); ip2 = power(p2, MOD2 - 2, MOD2); ipw[0] = {1, 1}; for (int i = 1; i < N; i++) { ipw[i].first = 1LL * ipw[i - 1].first * ip1 % MOD1; ipw[i].second = 1LL * ipw[i - 1].second * ip2 % MOD2; } } struct Hashing { int n; string s; // 0 - indexed vector<pair<int, int>> hs; // 1 - indexed Hashing() { } Hashing(string _s) { n = _s.size(); s = _s; hs.emplace_back(0, 0); for (int i = 0; i < n; i++) { pair<int, int> p; p.first = (hs[i].first + 1LL * pw[i].first * s[i] % MOD1) % MOD1; p.second = (hs[i].second + 1LL * pw[i].second * s[i] % MOD2) % MOD2; hs.push_back(p); } } pair<int, int> get_hash(int l, int r) { // 1 - indexed assert(1 <= l && l <= r && r <= n); pair<int, int> ans; ans.first = (hs[r].first - hs[l - 1].first + MOD1) * 1LL * ipw[l - 1].first % MOD1; ans.second = (hs[r].second - hs[l - 1].second + MOD2) * 1LL * ipw[l - 1].second % MOD2; return ans; } pair<int, int> get_hash() { return get_hash(1, n); } }; bool ispal(int l, int r, Hashing &hs, Hashing &hr) { return hs.get_hash(l, r) == hr.get_hash(n - r + 1, n - l + 1); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int tt; prec(); cin >> tt; while (tt--) { cin >> s; r = s; reverse(all(r)); n = s.size(); Hashing hs(s), hr(r); int mx = 0; for (int i = 1; i <= n; i++) { for (int j = i; j <= n; j++) { if (ispal(i, j, hs, hr)) { // cout << i << " " << j << '\n'; mx = max(mx, j - i + 1); } } } cout << mx << '\n'; } }
Leave a Comment