This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5 + 7;
struct node{
int len, cnt;
node *nxt[26], *suf;
node(int _len = 0){
len = _len;
cnt = 0;
for(int i = 0; i < 26; i++)
nxt[i] = nullptr;
suf = nullptr;
}
};
string s;
node *root1, *root2, *cur;
vector <node*> a[N];
void insert(int pos){
int id = s[pos] - 'a';
if (pos - cur->len - 1 < 0)
cur = cur->suf;
while(s[pos] != s[pos - cur->len - 1])
cur = cur->suf;
if (cur->nxt[id] != nullptr){
cur = cur->nxt[id];
return;
}
cur->nxt[id] = new node(cur->len + 2);
if (cur == root1){
cur->nxt[id]->suf = root2;
} else {
node *tmp = cur->suf;
while(s[pos] != s[pos - tmp->len - 1])
tmp = tmp->suf;
cur->nxt[id]->suf = tmp->nxt[id];
}
cur = cur->nxt[id];
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> s;
root1 = new node(-1);
root2 = new node(0);
root2->suf = root1;
cur = root2;
for(int i = 0; i < (int) s.size(); i++){
insert(i);
a[cur->len].push_back(cur);
cur->cnt++;
}
ll res = 0;
for(int i = s.size(); i >= 1; i--)
for(node *cur : a[i]){
res = max(res, (ll) cur->len * cur->cnt);
cur->suf->cnt += cur->cnt;
cur->cnt = 0;
}
cout << res;
return 0;
}
# | 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... |