题解
Hash和DP。
实际上也可以拿trie做。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
using namespace std;
typedef unsigned int ui;
char t[1000005];
bool able[1000005]={0};
int n,m,lth[25];
ui hsh[25],h[1000005],P=1005257,Pow[1000005];
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++){
scanf("%s",t);
hsh[i]=0,lth[i]=strlen(t);
for(int j=0;j<lth[i];j++)
hsh[i]=P*hsh[i]+t[j];
}
Pow[0]=1;
for(int i=1;i<=1000000;i++)
Pow[i]=Pow[i-1]*P;
for(int i=0;i<m;i++){
scanf("%s",t);
int len=strlen(t),ans=0,j,k;
h[0]=0,able[0]=1;
for(j=1;j<=len;j++){
h[j]=h[j-1]*P+t[j-1];
for(k=0;k<n;k++){
if(lth[k]<=j&&h[j]-Pow[lth[k]]*h[j-lth[k]]==hsh[k])
able[j]|=able[j-lth[k]];
if(able[j])break;
}
if(able[j])ans=j;
}
printf("%d\n",ans);
memset(able,0,sizeof(able));
}
return 0;
}