#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define debug if(0)
const int N = 1e6 + 4;
const ll mod1 = 1e9 + 7, mod2 = 999999323, base = 2131;
ll powbase[N][2];
ll mul(ll a, ll b, ll mod) { return (a*b)%mod; }
ll del(ll a, ll b, ll mod) {
a -= b;
a %= mod;
if(a < 0) a += mod;
return a;
}
struct H {
vector<ll> h1, h2;
int n;
H(string s) {
n = (int) s.size();
h1.assign(n+1, 0); h2.assign(n+1, 0);
for(int i=1; i<=n; i++) {
h1[i] = (mul(h1[i-1], base, mod1) + (s[i-1]-'a'+1))%mod1;
h2[i] = (mul(h2[i-1], base, mod2) + (s[i-1]-'a'+1))%mod2;
}
}
pair<ll, ll> substr(int l, int r) {
if(l > r) return {0, 0};
if(r > n) return {0, 0};
ll r1 = del(h1[r], mul(h1[l-1], powbase[r-l+1][0], mod1), mod1);
ll r2 = del(h2[r], mul(h2[l-1], powbase[r-l+1][1], mod2), mod2);
return {r1, r2};
}
};
void solve() {
string s; cin>>s; int n = (int) s.size();
H h(s);
int ans = 1, px = 0;
for(int i=1; i<=(n/2); i++) {
if(h.substr(px+1, i) == h.substr(n-i+1, n-px)) {
px = i;
ans+=2;
}
}
cout<<ans<<"\n";
}
void prepare() {
powbase[0][0] = powbase[0][1] = 1;
for(int i=1; i<N; i++) {
powbase[i][0] = mul(powbase[i-1][0], base, mod1);
powbase[i][1] = mul(powbase[i-1][1], base, mod2);
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
prepare();
int tc; cin>>tc;
while(tc--) {
solve();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
15956 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
15956 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
15956 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
15956 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
