이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int MOD = (int) 1e9 + 7;
const int p = 31;
/** Assumes 1 <= a, b < MOD */
int add(int a, int b) {
if (a + b >= MOD) return a + b - MOD;
return a + b;
}
/** Assumes 1 <= a, b < MOD */
int sub(int a, int b) {
return add(a, MOD - b);
}
/** Assumes 1 <= a, b < MOD */
int mul(int a, int b) {
return (long long) a * b % MOD;
}
/** Assumes 1 <= b < MOD */
int modpow(int b, int p) {
if (p == 0) return 1;
int ans = modpow(mul(b, b), p / 2);
if (p % 2 == 1) ans = mul(ans, b);
return ans;
}
int extgcd(int a, int b, int &x, int &y) {
if (b == 0) {
x = 1, y = 0;
return a;
}
int x1, y1, g = extgcd(b, a % b, x1, y1);
x = y1; y = sub(x1, mul(y1, (a / b) % MOD));
return g;
}
/** Assumes gcd(x, MOD) = 1 */
int inv(int x) {
int x1, y1;
extgcd(x, MOD, x1, y1);
return x1;
}
void solve() {
string s;
cin >> s;
int n = (int) s.length();
int ans = 0;
int l = 0, r = n - 1;
while (l <= r) {
bool found = false;
int l_hash = 0, r_hash = 0, pw = 1;
for (int i = l, j = r; i < j; i++, j--) {
l_hash = add(mul(p, l_hash), s[i] - 'a' + 1);
r_hash = add(r_hash, mul(pw, s[j] - 'a' + 1));
pw = mul(pw, p);
if (l_hash == r_hash && s.substr(l, i - l + 1) == s.substr(j, r - j + 1)) {
found = true;
l = i + 1; r = j - 1;
break;
}
}
if (!found) {
ans++;
break;
}
ans += 2;
}
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--) solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |