이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i<=b ; i++)
#define FORD(i, a, b) for (int i = a; i>=b; i--)
#define REP(i, a) for (int i = 0; i<a; i++)
#define N 300100
#define pp pair<int, int>
#define IO cin.tie(NULL);cout.tie(NULL);
template<typename T> inline void read(T &x) {
char c;
while (!isdigit(c = getchar()));
x = 0;
do {
x = x * 10 + c - '0';
} while (isdigit(c = getchar()));
}
template<typename T> inline void write(T x) {
if (x < 10) {
putchar(char(x + 48));
}
else {
write(x/10);
putchar(char(48 + x%10));
}
}
template<typename T> inline void writeln(T x) {
write(x);
putchar('\n');
}
using namespace std;
struct Node {
int next[26];
int suff, len;
long long cnt;
};
struct PalindromicTree {
vector<Node> tree;
int n, currNode, ptr;
string st;
vector<vector<int> > e;
void reset(string st) {
n = st.size();
this -> st = st;
tree.resize(n + 3);
e.resize(n + 3);
currNode = 0;
tree[0].len = -1;tree[0].suff = 0;
tree[1].len = 0;tree[1].suff = 0;
ptr = currNode = 1;
REP(i, n) add(i);
}
long long getAns() {
dfs(1);
long long ans = 0;
FOR(i, 2, ptr) {
ans = max(ans, 1ll * tree[i].cnt * tree[i].len);
}
return ans;
}
void add(int pos) {
int idx = st[pos] - 'a';
int cur = currNode;
while (true) {
int curLen = tree[cur].len;
if (pos - curLen >= 1 && st[pos] == st[pos - curLen - 1]) break;
cur = tree[cur].suff;
}
if (tree[cur].next[idx]) {
currNode = tree[cur].next[idx];
tree[currNode].cnt++;
return;
}
currNode = ++ptr;
tree[cur].next[idx] = ptr;
tree[ptr].cnt = 1;
tree[ptr].len = tree[cur].len + 2;
if (tree[ptr].len == 1) {
tree[ptr].suff = 1;
e[1].push_back(ptr);
return;
}
cur = tree[cur].suff;
while (true) {
int curLen = tree[cur].len;
if (pos - curLen >= 1 && st[pos] == st[pos - curLen - 1]) {
tree[currNode].suff = tree[cur].next[idx];
e[tree[cur].next[idx]].push_back(ptr);
return;
}
cur = tree[cur].suff;
}
}
void dfs(int u) {
for (int v : e[u]) {
dfs(v);
tree[u].cnt += tree[v].cnt;
}
}
}PT;
char s[N];
string st;
int main() {
IO;
scanf("%s", s);
string st = s;
PT.reset(st);
write(PT.getAns());
}
컴파일 시 표준 에러 (stderr) 메시지
palindrome.cpp: In function 'int main()':
palindrome.cpp:111:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", s);
^
# | 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... |