이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
struct eerTree {
struct state {
int nxt[26], len, link, cnt;
state(int len, int link, int cnt):
len(len), link(link), cnt(cnt) {
memset(nxt, 0, sizeof nxt);
}
};
vector <state> tree;
string s; int last;
vector <int> topo;
void extend(int pos) {
int chr = s[pos] - 'a', cur = last;
while (pos - tree[cur].len <= 0 ||
s[pos - tree[cur].len - 1] != s[pos])
cur = tree[cur].link;
if (tree[cur].nxt[chr]) {
last = tree[cur].nxt[chr];
tree[last].cnt++; return;
}
last = tree.size();
tree.emplace_back(tree[cur].len + 2, 0, 1);
tree[cur].nxt[chr] = last;
if (cur == 0) {
tree[last].link = 1; return;
}
cur = tree[cur].link;
while (pos - tree[cur].len <= 0 ||
s[pos - tree[cur].len - 1] != s[pos])
cur = tree[cur].link;
tree[last].link = tree[cur].nxt[chr];
}
eerTree(string s): s(s) {
tree.emplace_back(-1, 0, 0);
tree.emplace_back(0, 0, 0);
for (int i = 0; i < s.size(); i++)
extend(i);
vector <int> cnt(s.size() + 1);
for (int i = 2; i < tree.size(); i++)
cnt[tree[i].len]++;
for (int i = 1; i <= s.size(); i++)
cnt[i] += cnt[i - 1];
topo.resize(tree.size() - 2);
iota(topo.begin(), topo.end(), 2);
for (int i = 2; i < tree.size(); i++)
topo[--cnt[tree[i].len]] = i;
for (int i = topo.size() - 1; i >= 0; i--) {
int cur = topo[i];
tree[tree[cur].link].cnt += tree[cur].cnt;
}
}
long long maxOccurrenceValue() {
long long val = 0;
for (int i : topo)
val = max(val, 1ll * tree[i].len * tree[i].cnt);
return val;
}
};
int main() {
cin.tie(0)->sync_with_stdio(0);
string s; cin >> s; eerTree eT(s);
cout << eT.maxOccurrenceValue() << '\n';
}
컴파일 시 표준 에러 (stderr) 메시지
palindrome.cpp: In constructor 'eerTree::eerTree(std::string)':
palindrome.cpp:44:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | for (int i = 0; i < s.size(); i++)
| ~~^~~~~~~~~~
palindrome.cpp:47:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<eerTree::state>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | for (int i = 2; i < tree.size(); i++)
| ~~^~~~~~~~~~~~~
palindrome.cpp:49:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for (int i = 1; i <= s.size(); i++)
| ~~^~~~~~~~~~~
palindrome.cpp:53:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<eerTree::state>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for (int i = 2; i < tree.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... |