# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
308041 | Elephant52 | Palindromes (APIO14_palindrome) | C++11 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pair<int, int> > vpi;
#define INF 1000000000
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define rep(i,a,b) for (int i = a; i < b; i++)
void setIO(string name) {
freopen((name+".in").c_str(), "r", stdin);
freopen((name+".out").c_str(), "w", stdout);
}
string s;
typedef struct node {
int next[26];
ll len = 0, suflink = 0, num = 0;
node() {};
} node;
node tree[300001];
int num, suf;
vi adj[300001];
bool add_letter(int pos) { //return 1 on new palindromes
int cur = suf, letter = (s[pos]-'a'), curlen = 0;
while(1) { //find longest palindromic suffix of s[0...pos-1] that can include s[pos]
curlen = tree[cur].len;
if (pos > curlen && s[pos-1-curlen] == s[pos]) break;
cur = tree[cur].suflink;
}
if (tree[cur].next[letter]) { //if there exists a link from smaller palindrome to s[pos] + pal + s[pos] then do nothing
suf = tree[cur].next[letter];
tree[suf].num++;
return 0;
}
//create a new palindrome with id num+1 in the tree
suf = ++num;
tree[num].num = 1;
tree[num].len = tree[cur].len + 2; //add on s[pos]
tree[cur].next[letter] = num;
if (tree[num].len == 1) {
tree[num].suflink = 2; //link to the empty palindrome
adj[2].PB(num);
return 1;
}
while(1) {
cur = tree[cur].suflink;
curlen = tree[cur].len;
if (pos > curlen && s[pos-1-curlen] == s[pos]) {
tree[num].suflink = tree[cur].next[letter];
adj[tree[cur].next[letter]].PB(num);
break;
}
}
return 1;
}
void dfs(int cur = 1, par = -1) {
for (auto edge : adj[cur]) {
if (edge != par) {
dfs(edge, cur);
tree[cur].num += tree[edge].num;
}
}
}
void init() {
num = suf = 2;
tree[1].len = -1, tree[2].len = 0;
tree[1].suflink = tree[2].suflink = 1;
adj[1].PB(2);
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> s;
init();
rep(i,0,s.length()) add_letter(i);
ll ans = 0;
dfs();
rep(i,1,300001) ans = max(ans, tree[i].len * tree[i].num);
cout << ans << endl;
return 0;
}