#include <bits/stdc++.h> using namespace std; #define all(x) (x).begin(), (x).end() #define int long long #define pii pair<int, int> #define ms(x) memset((x), -1, sizeof (x)) #define FOR(i, a, b) for (int i = (a); i <= (b); ++i) const int MAX = (int) 1e6 + 5; const int MOD = (int) 1e9 + 7; const int BASE = 347; int T; int total; string S[MAX], s; bool maximize(int &x, const int &y){ if (x < y){ x = y; return 1; } return 0; } namespace sub2{ bool check(){ return (int)s.size() <= 300 && total <= 1800; } void solve(){ int n = s.size(); int f[n + 5][n + 5]; memset(f, 0, sizeof f); s = " " + s; for (int i = 1; i <= n / 2; i++){ for (int len = 1; len <= n / 2; len++){ if (i + len - 1 < n - i + 1 - len + 1){ bool ok = 1; for (int j = i; j <= i + len - 1; j++){ ok &= (s[j] == s[n - i + 1 - len + 1 + (j - i)]); } if (ok) f[i][len] = 1; } else break; } } int dp[n + 5]; memset(dp, 0, sizeof dp); for (int i = 1; i <= n / 2; i++){ for (int len = 1; len <= n / 2; len++){ if (f[i][len]) maximize(dp[i + len], dp[i] + 1); } } int res = 1; for (int i = 1; i <= n; i++){ if (dp[res] < dp[i]) res = i; } int answer = dp[res] << 1; if (n & 1 || res < n / 2) answer++; cout << answer << "\n"; } } namespace sub3{ bool check(){ return (int)s.size() <= 5000 && total <= 30000; } void solve(){ int n = s.size(); s = " " + s; int Pw[n + 5], H[n + 5]; Pw[0] = 1, H[0] = 1; for (int i = 1; i <= n; i++) Pw[i] = Pw[i - 1] * BASE % MOD; for (int i = 1; i <= n; i++) H[i] = (H[i - 1] * BASE + (s[i] - 'a' + 1)) % MOD; auto ask = [&](const int &l, const int &r) -> int{ return (H[r] - H[l - 1] * Pw[r - l + 1] % MOD + MOD) % MOD; }; int f[n + 5][n + 5]; memset(f, 0, sizeof f); for (int i = 1; i <= n / 2; i++){ for (int len = 1; len <= n / 2; len++){ if (i + len - 1 < n - i + 1 - len + 1){ bool ok = ask(i, i + len - 1) == ask(n - i + 1 - len + 1, n - i + 1); if (ok) f[i][len] = 1; } else break; } } int dp[n + 5]; memset(dp, 0, sizeof dp); for (int i = 1; i <= n / 2; i++){ for (int len = 1; len <= n / 2; len++){ if (f[i][len]) maximize(dp[i + len], dp[i] + 1); } } int res = 1; for (int i = 1; i <= n; i++){ if (dp[res] < dp[i]) res = i; } int answer = dp[res] << 1; if (n & 1 || res < n / 2) answer++; cout << answer << "\n"; } } namespace greedy{ bool check(){ return 1; } void solve(){ int n = s.size(); s = " " + s; int Pw[n + 5], H[n + 5]; Pw[0] = 1, H[0] = 1; for (int i = 1; i <= n; i++) Pw[i] = Pw[i - 1] * BASE % MOD; for (int i = 1; i <= n; i++) H[i] = (H[i - 1] * BASE + (s[i] - 'a' + 1)) % MOD; auto ask = [&](const int &l, const int &r) -> int{ return (H[r] - H[l - 1] * Pw[r - l + 1] % MOD + MOD) % MOD; }; int answer = 0, prev = 1; for (int i = 1; i <= n / 2; i++){ int len = i - prev + 1; if (ask(prev, i) == ask(n - prev + 1 - len + 1, n - prev + 1)){ answer++; prev = i + 1; } } answer <<= 1; if (prev != n / 2 + 1 || n & 1) answer++; cout << answer << "\n"; } } signed main(){ #define name "sixcup" if (fopen(name".inp", "r")){ freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); } ios::sync_with_stdio(false); cin.tie(nullptr); cin >> T; for (int i = 1; i <= T; i++){ cin >> S[i]; total += S[i].size(); } for (int i = 1; i <= T; i++){ s = S[i]; // if (sub2::check()) {sub2::solve(); continue;} // if (sub3::check()) {sub3::solve(); continue;} if (greedy::check()) {greedy::solve(); continue;} } return 0; }

palindromic.cpp: In function 'int main()':
palindromic.cpp:149:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  149 |         freopen(name".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
palindromic.cpp:150:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  150 |         freopen(name".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~