#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define vl vector<ll>
#define vi vector<int>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(v) v.begin(), v.end()
#define pb push_back
#define f first
#define s second
using namespace std;
using namespace __gnu_pbds;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const ll sz = 1e6+5, mod = 1e9+7, P = 47;
ll p[sz], h[sz], n, i;
bool check(ll a, ll b, ll k)
{
ll h1 = (h[a + k - 1] - h[a - 1] + mod) % mod;
ll h2 = (h[b + k - 1] - h[b - 1] + mod) % mod;
return (h1 * 1LL * p[b - a]) % mod == h2;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll tests = 1;
cin >> tests;
while(tests--)
{
string s;
cin >> s;
n = s.size();
p[0] = 1;
for(i = 1; i <= n; i++)
p[i] = (p[i-1] * P * 1LL) % mod;
for(i = 1; i <= n; i++)
h[i] = (h[i-1] + ((s[i - 1] - 'a' + 1) * 1LL * p[i-1])) % mod;
ll ans = 0, l = 1, r = n, k = 1;
while(l < r)
{
ll a = l - k + 1;
if(check(a, r, k))
{
ans++;
k = 1;
}
else
k++;
l++;
r--;
}
cout << ans * 2 + 1 << "\n";
for(i = 0; i <= n; i++)
{
h[i] = 0;
p[i] = 0;
}
n = 0;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
