#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(), x.end()
const int M = 200007;
const ll inf = 1e18;
const ll mod = 998244353;
const double pi = acos(-1);
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
struct Hash {
ll SEED = 31,MOD = 1e9 + 7;
vector<ll> ha;
vector<ll> power;
void build(string x) {
power.resize(x.size());
ha.resize(x.size());
power[0] = 1;
for(int i=1; i<(int)power.size(); i++) power[i] = (power[i-1] * SEED)%MOD;
ha[0] = x[0];
for(int i=1; i<(int)ha.size(); i++) ha[i] = (ha[i-1] * SEED + x[i])%MOD;
}
ll get(int i, int j) {
ll ret = ha[j];
if (i) ret -= (ha[i-1] * power[j - i + 1])%MOD;
ret = (ret % MOD + MOD) % MOD;
return ret;
}
};
int main()
{
int t; cin >> t;
while(t--){
string s;
cin >> s;
Hash Hs; Hs.build(s);
int n = s.size(), st = 0, ans = 0;
for(int i = 0; i < n / 2; ++i){
if(Hs.get(st, i) == Hs.get(n - i - 1, n - st - 1)){
ans += 2;
st = i + 1;
}
}
cout << ans + 1 << endl;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
