이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
#define out(x) "{" << (#x) << ": " << x << "} "
const int MAX_N = 1e5 + 10;
struct PalindromicTree {
map<char, int> mp[MAX_N];
int link[MAX_N], len[MAX_N], times[MAX_N];
int cnt, last;
void init() {
for(int i = 0; i < cnt; i ++) {
mp[i].clear();
}
cnt = 2;
last = 1;
len[0] = -1; link[0] = 0;
len[1] = 0; link[1] = 0;
}
void build(const string &text) {
for(int i = 0; i < text.size(); i ++) {
while(true) {
if(text[i - len[last] - 1] == text[i]) {
int curr;
if(mp[last].find(text[i]) == mp[last].end()) {
curr = cnt ++;
mp[last][text[i]] = curr;
} else {
curr = mp[last][text[i]];
}
len[curr] = len[last] + 2;
while(last != 0 && (mp[last].find(text[i]) == mp[last].end() || mp[last][text[i]] == curr)) {
last = link[last];
}
if(mp[last].find(text[i]) == mp[last].end() || mp[last][text[i]] == curr) {
link[curr] = 1;
} else {
link[curr] = mp[last][text[i]];
}
last = curr;
break;
} else {
last = link[last];
}
}
times[last] ++;
}
}
int getAns() {
int ret = -1;
for(int i = cnt - 1; i >= 0; i --) {
times[link[i]] += times[i];
chkmax(ret, (ll)times[i] * (ll)len[i]);
}
return ret;
}
};
PalindromicTree pt;
signed main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
string in;
cin >> in;
pt.init();
pt.build(in);
cout << pt.getAns() << endl;
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
palindrome.cpp: In member function 'void PalindromicTree::build(const string&)':
palindrome.cpp:29:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | for(int i = 0; i < text.size(); 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... |