社区讨论
90分,第四个点WA
P2292[HNOI2004] L 语言参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @mi6lg14b
- 此快照首次捕获于
- 2025/11/20 06:48 4 个月前
- 此快照最后确认于
- 2025/11/20 06:48 4 个月前
CPP
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
#define fo(a,b,c) for(int a=b;a<=c;a++)
int read(){
int a=0,f=0;char c=getchar();
for(;c<'0'||c>'9';c=getchar())if(c=='-')f=1;
for(;c>='0'&&c<='9';c=getchar())a=a*10+c-'0';
return f?-a:a;
}
const int N=1e5;
int son[N][26],count[N],len[N],fail[N],q[N],able[10];
string s;
int main(){
//freopen("in.txt","r",stdin);
int n=read(),m=read(),cnt=0;
fo(i,1,n){
cin>>s;int p=0;len[i]=s.length();
fo(j,0,len[i]-1){
int idx=s[j]-'a';
if(!son[p][idx])
son[p][idx]=++cnt;
p=son[p][idx];
}
count[p]=1<<i;
}
for(int st=0,ed=0;st<=ed;st++){
int u=q[st];
count[u]|=count[fail[u]];
fo(i,0,25){
int v=son[u][i];
if(v)q[++ed]=v;
else son[u][i]=son[fail[u]][i];
if(u&&v)fail[v]=son[fail[u]][i];
}
}
fo(i,1,m){
cin>>s;
memset(able,0,sizeof(able));able[9]=1;
int ans=0,p=0,j,sum=1;
for(j=0;j<s.length();able[(++j)%10]=0){
int idx=s[j]-'a';
p=son[p][idx];
for(int x=count[p]>>1,k=1;x;x>>=1,k++)if(x&1)
able[j%10]|=able[(j-len[k]+10)%10];
sum+=able[j%10]-able[(j+1)%10];
if(!sum)break;
}
if(!sum){printf("%d\n",j-8);continue;}
while(!able[j%10])j--;
printf("%d\n",j+1);
}
return 0;
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...