이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
const int Z = 3e5+2, B = 26;
int sz[Z] = {-1}, sLink[Z], cnt[Z], cur = 2, p = 1;
map<int, int> c[Z];
int n, __s[Z] {-1}, *s = __s + 1;
string _s;
int main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> _s;
n = _s.size();
for(int i = 0; i < n; ++i) {
s[i] = _s[i] - 'a';
for(; s[i-sz[p]-1] != s[i]; p = sLink[p]);
if(!c[p][s[i]]) {
int &v = (sLink[cur] = sLink[p]);
for(; s[i-sz[v]-1] != s[i]; v = sLink[v]);
sz[cur] = sz[p] + 2;
c[p][s[i]] = cur;
v = sz[v] + 2 < sz[cur] ? c[v][s[i]] : 1;
cur++;
}
++cnt[p = c[p][s[i]]];
}
i64 res {};
for(int u = cur; u--; ) {
res = max(res, i64(cnt[u]) * sz[u]);
cnt[sLink[u]] += cnt[u];
}
cout << res;
}
# | 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... |