# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
101380 | KCSC | 회문 (APIO14_palindrome) | C++14 | 2 ms | 412 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
class Eertree {
private:
struct Node {
map<char, int> son;
int length, suffixLink, start, end, psm = 0;
vector<int> lnk;
Node(int _length = 0, int _start = 0, int _end = 0) :
length(_length), suffixLink(0), start(_start), end(_end) {}
};
int last;
vector<Node> tree;
string myString;
void _addLetter(char ch) {
int idx = myString.length(), tmp = last;
myString.push_back(ch);
while (true) {
int len = tree[tmp].length;
if (idx - len and myString[idx - len - 1] == myString[idx]) {
break; }
tmp = tree[tmp].suffixLink; }
if (tree[tmp].son.find(ch) != tree[tmp].son.end()) {
last = tree[tmp].son[ch];
return; }
tree.push_back(Node(tree[tmp].length + 2, idx - tree[tmp].length - 1, idx));
last = tree[tmp].son[ch] = tree.size() - 1; tmp = tree[tmp].suffixLink;
if (tree[last].length == 1) {
tree[last].suffixLink = 1;
tree[1].lnk.push_back(last);
return; }
while (true) {
int len = tree[tmp].length;
if (idx - len and myString[idx - len - 1] == myString[idx]) {
break; }
tmp = tree[tmp].suffixLink; }
tree[last].suffixLink = tree[tmp].son[ch]; tree[tree[tmp].son[ch]].lnk.push_back(last);
return; }
void dfs(int x, long long &ans) {
for (int y : tree[x].lnk) {
dfs(y, ans); tree[x].psm += tree[y].psm; }
if (x >= 2) {
ans = max(ans, 1LL * (tree[x].end - tree[x].start + 1) * tree[x].psm); } }
public:
Eertree() : last(0) {
tree.push_back(Node(-1));
tree.push_back(Node( 0)); }
Eertree(const string str) : last(0) {
tree.push_back(Node(-1));
tree.push_back(Node( 0));
for (char ch : str) {
_addLetter(ch); } }
void addLetter(const char ch) {
_addLetter(ch); }
void addString(const string str) {
for (char ch : str) {
_addLetter(ch); } }
void debug(const string str) {
for (char ch : str) {
_addLetter(ch); ++tree[last].psm; }
long long ans = 0; dfs(0, ans); dfs(1, ans);
cout << tree.size() - 2 << endl;
for (int i = 2; i < tree.size(); ++i) {
for (int j = tree[i].start; j <= tree[i].end; ++j) {
cout << myString[j]; }
cout << " " << tree[i].psm << endl; } }
long long solve(const string str) {
tree[0].lnk.push_back(1);
for (char ch : str) {
_addLetter(ch); ++tree[last].psm; }
long long ans = 0; dfs(0, ans);
return ans; }
} myEertree;
int main(void) {
freopen("palindrome.in", "r", stdin);
freopen("palindrome.out", "w", stdout);
string str; cin >> str;
cout << myEertree.solve(str);
return 0; }
컴파일 시 표준 에러 (stderr) 메시지
# | 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... |