제출 #966851

#제출 시각아이디문제언어결과실행 시간메모리
966851OmarAlimammadzadePalindromic Partitions (CEOI17_palindromic)C++14
0 / 100
7 ms5980 KiB
#include <bits/stdc++.h> using namespace std; const int N = 1e6 + 1; int p[N], h[N], P = 47, M = 1e9 + 7, n; bool checkEqual(int a, int b, int l) { int ha = (h[a + l - 1] - h[a - 1] + M) % M; int hb = (h[b + l - 1] - h[b - 1] + M) % M; return hb == 1ll * ha * p[b - a] % M; } int main() { int t; cin >> t; p[0] = 1; for (int i = 1; i < N; i++) p[i] = 1ll * p[i - 1] * P % M; while (t--) { string s; cin >> s; int n = s.size(); for (int i = 1; i <= n; i++) h[i] = (h[i - 1] + 1ll * (s[i - 1] - 'a' + 1) * p[i - 1] % M) % M; int l = 1, r = n, res = 0, k = 1; while (l <= r) { if (checkEqual(l, r - k + 1, k)) { if (l + k < r) res++; res++; l += k; r -= k; k = 1; } else k++; } cout << res << endl; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...