[POJ2774] 롱롱 메시지 접미사 로봇
코드만 붙이고,
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 101000
#define T 30
using namespace std;
char s[N],t[N];
int pa[N<<1],son[N<<1][T];
int deep[N<<1],cnt,root,last;
inline int Newnode(int _deep){deep[++cnt]=_deep;return cnt;}
inline void SAM(int alp)
{
int u=last;
last=Newnode(deep[last]+1);
while(u&&!son[u][alp])son[u][alp]=last,u=pa[u];
if(!u)pa[last]=root;
else {
int v=son[u][alp];
if(deep[v]==deep[u]+1)pa[last]=v;
else {
int nv=Newnode(deep[u]+1);
memcpy(son[nv],son[v],sizeof son[v]);
pa[nv]=pa[v],pa[v]=pa[last]=nv;
while(u&&son[u][alp]==v)son[u][alp]=nv,u=pa[u];
}
}
}
int lena,lenb;
int solve(int n)
{
int i,x,v,ret=0,temp=0;
x=root=last=Newnode(0);
for(i=1;i<=lena;i++)SAM(s[i]-'a');
for(i=1;i<=lenb;i++)
{
if(son[x][t[i]-'a'])x=son[x][t[i]-'a'],temp++;
else {
while(x&&son[x][t[i]-'a']==0)x=pa[x];
if(!x)x=root,temp=0;
else temp=deep[x]+1,x=son[x][t[i]-'a'];
}
ret=max(ret,temp);
}
return ret;
}
int main()
{
// freopen("test.in","r",stdin);
int i,j,n,ans=0;
scanf("%s %s",s+1,t+1);
lena=strlen(s+1),lenb=strlen(t+1);
printf("%d
",solve(n));
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[CTSC2012] 익숙한 글제목의 뜻 여러 개의 주열이 있고, 매번 문의할 때마다 질문열을 여러 개의 연속 서브열로 나누며, 만약 한 서브열의 길이가 ≥L≥L이고 주열에 나타난 적이 있다면 합법적이다 만약 합법적인 하위 문자열의 총 길이가 ≥...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
