이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <stdio.h>
#include <bits/stdc++.h>
#define pb push_back
#define pf push_front
#define pp pop_back
#define sz(a) (int)(a.size())
#define mp make_pair
#define F first
#define S second
#define next _next
#define prev _prev
#define left _left
#define right _right
#define y1 _y1
#define all(x) x.begin(), x.end()
#define what_is(x) #x << " is " << (x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int N = (int)1e4 + 123;
const ll INF = (ll)1e18 + 123;
const int inf = (int)1e9 + 123;
const int MOD = (int)4e7 + 7;
const int P = 47;
int mult(int a, int b) {
return 1ll * a * b % MOD;
}
int add(int a, int b) {
a += b;
if(a >= MOD) a -= MOD;
return a;
}
int subs(int a, int b) {
a -= b;
if(a < 0) a += MOD;
return a;
}
string s;
int cnt[(int)4e7 + 7];
//map<int, int> cnt;
int pw[N];
int h[N];
int get_hash(int l, int r) {
return subs(h[r], mult(h[l - 1], pw[r - l + 1]));
}
int main() {
pw[0] = 1;
for(int i = 1; i <= N - 123; i ++)
pw[i] = mult(pw[i - 1], P);
cin >> s;
//cnt.reserve(500000);
h[0] = s[0];
for(int i = 1; i < sz(s); i ++)
h[i] = add(mult(h[i - 1], P), s[i]);
int res = 0, len, i;
for(i = 0; i < sz(s); i ++) {
len = 1;
cnt[s[i]] ++;
while(i - len >= 0 && i + len < sz(s) && s[i - len] == s[i + len]) {
cnt[get_hash(i - len, i + len)] ++;
len ++;
}
}
for(i = 0; i < sz(s); i ++) {
len = 1;
res = max(res, cnt[s[i]]);
while(i - len >= 0 && i + len < sz(s) && s[i - len] == s[i + len]) {
res = max(res, (len * 2 + 1) * cnt[get_hash(i - len, i + len)]);
len ++;
}
}
//_____________________________________________
for(i = 0; i < sz(s); i ++) {
len = 0;
while(i - len - 1 >= 0 && i + len < sz(s) && s[i - len - 1] == s[i + len]) {
cnt[get_hash(i - len - 1, i + len)] ++;
len ++;
}
}
for(i = 0; i < sz(s); i ++) {
len = 0;
while(i - len - 1 >= 0 && i + len < sz(s) && s[i - len - 1] == s[i + len]) {
res = max(res, (len + 1) * 2 * cnt[get_hash(i - len - 1, i + len)]);
len ++;
}
}
cout << res;
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
palindrome.cpp: In function 'int main()':
palindrome.cpp:72:11: warning: array subscript has type 'char' [-Wchar-subscripts]
cnt[s[i]] ++;
^
palindrome.cpp:80:26: warning: array subscript has type 'char' [-Wchar-subscripts]
res = max(res, cnt[s[i]]);
^
# | 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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |