# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
101380 | 2019-03-18T20:22:14 Z | KCSC | Palindromes (APIO14_palindrome) | C++14 | 2 ms | 412 KB |
#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; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 384 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 384 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 412 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 384 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 384 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |