hoi33:#include<bits/stdc++.h>
usingnamespacestd;
constintN=110*1100;
constintM=1024*1024+10;
intnxt[N][26],fail[N],endd[N];
inttot=0;
voidInsert(char*s)
{
intlen=strlen(s);
intu=0;
for(inti=0; i<len; i++)
{
intid=s[i];
if(nxt[u][id]==0) nxt[u][id]=++tot;
u=nxt[u][id];
}
endd[u]=1;
}
intquery(char*s,intlen)
{
intret=0,u=0;
for(inti=0; i<len; i++)
{
intt=nxt[u][s[i]];
u=t;
if(endd[t])
{
ret=i+1;
if(i+1==len)
break;
if(nxt[t][s[i+1]]==0)
u=0;
}
if(t==0)
break;
}
returnret;
}
charstr[1100][110],s[50*M];
intn,m;
charsnew[100*M];
intp[100*M];
intminn(intx,inty)
{
returnx>y?y:x;
}
intmaxn(intx,inty)
{
returnx>y?x:y;
}
intinit(intlen)
{
snew[0]='$',snew[1]='#';
intj=2;
for(inti=0; i<len; i++)
{
snew[j++]=s[i];
snew[j++]='#';
}
snew[j]='\0';
returnj;
}
intMan(intlen)
{
intmax_len=-1,id,mx=0;
for(inti=1; i<len; i++)
{
if(i<mx)
p[i]=minn(p[2*id-i],mx-i);
else
p[i]=1;
while(snew[i-p[i]]==snew[i+p[i]])
p[i]++;
if(mx<i+p[i])
id=i,mx=i+p[i];
max_len=maxn(max_len,p[i]-1);
}
returnmax_len;
}
intmain()
{
scanf("%d%d",&n,&m);
for(inti=1; i<=n; i++)
{
scanf("%s",str[i]);
Insert(str[i]);
}
while(m--)
{
scanf("%s",s);
intlen=query(s,strlen(s));
intlen1=Man(init(len));
printf("%d %d\n",len,len1);
}
return0;
}
I题有毒吧,这道题1M究竟有多大,而且开了这么大才44MS 你确定没有错
0 点赞 评论 收藏
分享
0 点赞 评论 收藏
分享
创作者周榜
更多
关注他的用户也关注了: