BZOJ3676: [Apio2014] 메모
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
struct Node
{
int len;
Node *ch[31];
Node *last;
int num;
Node(){for(len=0;len<=30;len++)ch[len]=NULL;last=NULL;len=num=0;}
};
Node*Max_Node,*Node_2,*Node_1;
int num;
Node *Stack[400001];
int top;
inline Node *New_Node()
{
Node *res=new Node;
Stack[top++]=res;
return res;
}
char s[400001];
inline void begin(){Node_2=new Node;Node_1=new Node;Max_Node=Node_2;num=2;Node_2->last=Node_1->last=Node_1;Node_1->len=-1;Node_2->len=0;}
inline bool add(int place)
{
bool Exit=false;
Node *cur=Max_Node;
int curlen=0,son=s[place]-'a';
while(true)
{
curlen=cur->len;
if(place-1-curlen>=0&&s[place-1-curlen]==s[place])
break;
cur=cur->last;
}
if(cur->ch[son])
Max_Node=cur->ch[son],cur->ch[son]->num++;
else
{
Exit=true;
Node*tp=New_Node();
Max_Node=tp;
tp->len=cur->len+2;
cur->ch[son]=tp;
if(tp->len==1)
tp->last=Node_2,tp->num=1;
else
{
while(true)
{
cur=cur->last;
curlen=cur->len;
if(place-1-curlen>=0&&s[place-1-curlen]==s[place])
{
Max_Node->last=cur->ch[son];
break;
}
}
Max_Node->num=1;
}
}
return Exit;
}
long long ans=-1;
inline void Calc()
{
Node *tp;
for(int i=top-1;i!=-1;i--)
{
tp=Stack[i];tp->last->num+=tp->num;
ans=max(ans,tp->num*1ll*tp->len);
}
}
char c;
int main()
{
int len=0;
do c=getchar();while(c<'a'||c>'z');
while(c<='z'&&c>='a')
s[len++]=c,c=getchar();
begin();
for(int i=0;i<len;i++)add(i);
Calc();
printf("%lld
",ans);
return 0;
}
그리고 못생긴 방법이 있어요. Manacher+SAM으로 때리고 싶지 않아요.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.