#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};
}
};
int sol(H &h, int l, int r) {
debug cerr<<"l, r = "<<l<<", "<<r<<"\n";
if(l > r) return 0;
for(int lx=l; lx <= r; lx++) {
int dl = lx - l;
int rx = r - dl;
if(lx >= rx) break;
if(h.substr(l, lx) == h.substr(rx, r)) return sol(h, lx+1, rx-1)+2;
}
return 1;
}
void solve() {
string s; cin>>s; int n = (int) s.size();
H h(s);
cout<<sol(h, 1, n)<<"\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();
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
14 ms |
15956 KB |
Output is correct |
| 2 |
Correct |
14 ms |
15912 KB |
Output is correct |
| 3 |
Correct |
14 ms |
15956 KB |
Output is correct |
| 4 |
Correct |
15 ms |
15980 KB |
Output is correct |
| 5 |
Correct |
14 ms |
15876 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
14 ms |
15956 KB |
Output is correct |
| 2 |
Correct |
14 ms |
15912 KB |
Output is correct |
| 3 |
Correct |
14 ms |
15956 KB |
Output is correct |
| 4 |
Correct |
15 ms |
15980 KB |
Output is correct |
| 5 |
Correct |
14 ms |
15876 KB |
Output is correct |
| 6 |
Correct |
14 ms |
15980 KB |
Output is correct |
| 7 |
Correct |
17 ms |
15956 KB |
Output is correct |
| 8 |
Correct |
15 ms |
15976 KB |
Output is correct |
| 9 |
Correct |
15 ms |
15956 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
14 ms |
15956 KB |
Output is correct |
| 2 |
Correct |
14 ms |
15912 KB |
Output is correct |
| 3 |
Correct |
14 ms |
15956 KB |
Output is correct |
| 4 |
Correct |
15 ms |
15980 KB |
Output is correct |
| 5 |
Correct |
14 ms |
15876 KB |
Output is correct |
| 6 |
Correct |
14 ms |
15980 KB |
Output is correct |
| 7 |
Correct |
17 ms |
15956 KB |
Output is correct |
| 8 |
Correct |
15 ms |
15976 KB |
Output is correct |
| 9 |
Correct |
15 ms |
15956 KB |
Output is correct |
| 10 |
Correct |
19 ms |
16260 KB |
Output is correct |
| 11 |
Correct |
15 ms |
16208 KB |
Output is correct |
| 12 |
Correct |
16 ms |
16248 KB |
Output is correct |
| 13 |
Correct |
18 ms |
16216 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
14 ms |
15956 KB |
Output is correct |
| 2 |
Correct |
14 ms |
15912 KB |
Output is correct |
| 3 |
Correct |
14 ms |
15956 KB |
Output is correct |
| 4 |
Correct |
15 ms |
15980 KB |
Output is correct |
| 5 |
Correct |
14 ms |
15876 KB |
Output is correct |
| 6 |
Correct |
14 ms |
15980 KB |
Output is correct |
| 7 |
Correct |
17 ms |
15956 KB |
Output is correct |
| 8 |
Correct |
15 ms |
15976 KB |
Output is correct |
| 9 |
Correct |
15 ms |
15956 KB |
Output is correct |
| 10 |
Correct |
19 ms |
16260 KB |
Output is correct |
| 11 |
Correct |
15 ms |
16208 KB |
Output is correct |
| 12 |
Correct |
16 ms |
16248 KB |
Output is correct |
| 13 |
Correct |
18 ms |
16216 KB |
Output is correct |
| 14 |
Correct |
360 ms |
43584 KB |
Output is correct |
| 15 |
Correct |
174 ms |
38120 KB |
Output is correct |
| 16 |
Correct |
323 ms |
41884 KB |
Output is correct |
| 17 |
Correct |
167 ms |
30856 KB |
Output is correct |
