Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- #define FOR(i, a, b) for(int i = a; i < b; ++i)
- #define REP(i, n) FOR(i, 0, n)
- #define _ << " " <<
- #define sz(x) ((int) x.size())
- #define pb(x) push_back(x)
- #define TRACE(x) cerr << #x << " = " << x << endl
- typedef long long ll;
- typedef pair<int, int> point;
- const int MAXN = 1e6 + 5, mod = 1e9 + 7, baza = 31337;
- int add(int x, int y) {x += y; if(x >= mod) return x - mod; return x;}
- int sub(int x, int y) {x -= y; if(x < 0) return x + mod; return x;}
- int mul(int x, int y) {return (ll) x * y % mod;}
- int h[MAXN], pot[MAXN];
- int calc(int x, int y){
- int k = 0;
- if(x) k = mul(h[x - 1], pot[y]);
- return sub(h[x + y - 1], k);
- }
- void solve(){
- string s; cin >> s;
- h[0] = s[0];
- pot[0] = 1;
- FOR(i, 1, sz(s)){
- h[i] = add( mul(h[i - 1], baza), s[i]);
- pot[i] = mul(pot[i - 1], baza);
- }
- int sol = 0, cnt = 0, last = -1;
- REP(i, sz(s) / 2){
- cnt ++;
- if( calc(i - cnt + 1, cnt) == calc(sz(s) - i - 1, cnt)){
- sol += 2;
- cnt = 0;
- last = i;
- }
- }
- if(sz(s) % 2) sol ++;
- else if(sz(s) % 2 == 0 && last != sz(s) / 2 - 1) sol ++;
- cout << sol << "\n";
- }
- int main(){
- ios_base::sync_with_stdio(false); cin.tie(0);
- int t; cin >> t;
- while(t --)
- solve();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement