#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
// author : a1abay
// (a / b) % c = (a * b ^ (mod - 2)) % c;
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(v) v.begin(), v.end()
#define whole(a) a+1, a+1+n
#define se second
#define fi first
#define int ll
#define print(k) cerr << "Ans : "; cout << k << endl;
#define ins insert
#define bpc __builtin_popcountll
#define skip continue
#define endll '\n'
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) (a*b / (__gcd(a, b)))
#define mpr make_pair
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int sz = 1e6 + 5;
using namespace std;
void open(string s, string f)
{
freopen((s + ".txt").c_str(), "r", stdin);
freopen((f + ".txt").c_str(), "w", stdout);
}
int mod = 1e9 + 7;
int P = 53;
int n, p[sz], pr[sz], sf[sz];
bool check(int l, int lx, int r, int rx)
{
int a = (pr[l] - pr[lx] + mod) % mod;
int b = (pr[rx - 1] - pr[r - 1] + mod) % mod;
return a * p[r - lx - 1] % mod == b;
}
void solve()
{
string s;
cin >> s;
n = s.size();
p[0] = 1;
for(int i = 1; i <= n; i++)
{
p[i] = p[i - 1] * P % mod;
pr[i] = pr[i - 1] + (s[i - 1] - 'a' + 1) * p[i] % mod;
}
int l = 1, r = n, lx = 0, rx = n + 1, ans = 1;
while(l < r)
{
if(check(l, lx, r, rx))
{
ans += 2;
lx = l;
rx = r;
}
l++;
r--;
}
cout << ans << '\n';
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// open("in", "out");
int t = 1;
cin >> t;
while(t--)
{
solve();
}
}
Compilation message
palindromic.cpp: In function 'void open(std::string, std::string)':
palindromic.cpp:35:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
35 | freopen((s + ".txt").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
palindromic.cpp:36:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
36 | freopen((f + ".txt").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
