| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 45432 | 2018-04-13T16:58:12 Z | Noam527 | Palindromic Partitions (CEOI17_palindromic) | C++11 | 0 ms | 0 KB |
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <string>
#include <time.h>
#include <stack>
#include <queue>
#include <random>
#include <fstream>
#define endl '\n'
#define flush fflush(stdout), cout.flush()
#define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define debug cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7, inf = 1e9 + 7;
const ll hs = 199;
const ldb eps = 1e-9, pi = acos(-1);
using namespace std;
const int maxn = 1e6 + 1;
const int p[3] = { 157, 163, 167 };
const int mod[3] = { 1e9 + 7, 1e9 + 9, 1e9 + 21 };
ll pw[3][maxn];
void preprocess() {
for (int i = 0; i < 3; i++) pw[i][0] = 1;
for (int j = 1; j < maxn; j++)
for (int i = 0; i < 3; i++)
pw[i][j] = (pw[i][j - 1] * p[i]) % mod[i];
}
void solve() {
string s;
cin >> s;
int n = s.size();
int ans = 0;
int st = 0;
ll sth[3] = {};
ll enh[3] = {};
bool ok;
for (int i = 0; i < n; i++) {
if (i >= n / 2) {
if (n % 2 == 1 || st < i) ans++;
cout << ans << endl;
return;
}
for (int j = 0; j < 3; j++) {
sth[j] = (sth[j] + pw[j][i - st] * s[i]) % mod[j];
enh[j] = (p[j] * enh[j] + s[n - i - 1]) % mod[j];
}
ok = true;
for (int j = 0; j < 3; j++) {
ok = ok && (sth[j] == enh[j]);
}
if (ok) {
ans += 2;
st = i + 1;
for (int j = 0; j < 3; j++)
sth[j] = enh[j] = 0;
}
}
}
int main() {
fast;
preprocess();
int t;
cin >> t;
while (t--) solve();
}