[BZOJ 3676] [APIO 2014] 댓 글 꼬치.
시간 복잡 도
【 코드 】
#include
using namespace std;
#define MAXN 300005
struct Palindromic_Tree {
int child[MAXN][26], father[MAXN];
int depth[MAXN], cnt[MAXN];
int size, last, len;
char s[MAXN];
int new_node(int length) {
memset(child[size], 0, sizeof(child[size]));
father[size] = 0;
depth[size] = length;
cnt[size] = 0;
return size++;
}
void Extend(int ch, int pos) {
int p = last;
while (s[pos - depth[p] - 1] != s[pos])
p = father[p];
if (!child[p][ch]) {
int now = new_node(depth[p] + 2), fa = father[p];
while (s[pos - depth[fa] - 1] != s[pos])
fa = father[fa];
father[now] = child[fa][ch];
if (father[now] == 0) father[now] = 1;
child[p][ch] = now;
}
last = child[p][ch];
cnt[last]++;
}
void init(char *x) {
len = strlen(x + 1);
for (int i = 1; i <= len; i++)
s[i] = x[i];
size = 0;
new_node(-1);
new_node(0);
father[0] = father[1] = 0;
depth[0] = -1;
last = 1;
for (int i = 1; i <= len; i++)
Extend(s[i] - 'a', i);
}
long long getans() {
long long ans = 0;
for (int i = size - 1; i > 0; i--) {
cnt[father[i]] += cnt[i];
ans = max(ans, (long long) cnt[i] * depth[i]);
}
return ans;
}
} PT;
char s[MAXN];
int main() {
scanf("%s", s + 1);
PT.init(s);
printf("%lld
", PT.getans());
return 0;
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[BZOJ 3676] [APIO 2014] 댓 글 꼬치.[제목 링크] 클릭 하여 링크 열기 [아이디어 포인트] 리 턴 트 리 템 플 릿 문제. 시간 복잡 도 【 코드 】...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
