就DP本身来说非常好想,但是怎样知道这个东西有没有在字典里出现过呢
hash似乎还是有点慢
这时候就应该用字典树了
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int f[300005];
int tr[400005][50];
string s;
int cnt;
int n;
int mod=20071027;
char oor[3000005];
int p;
int num[3000005];
void add(int l){
int x=0;
for(int i=0;i<l;++i){
int v=s[i]-'a';
if(!tr[x][v]){
tr[x][v]=++p;
}
x=tr[x][v];
}
num[x]++;
}
void que(int x,int l){
int no=0;
for(int i=x;i<=l;++i){
int v=oor[i]-'a';
if(!tr[no][v]) return ;
if(num[tr[no][v]]) f[x]+=f[i+1],f[x]%=mod;
no=tr[no][v];
}
}
int main(){
while(scanf("%s",oor+1)!=EOF){
cnt++;
int l=strlen(oor+1);
scanf("%d",&n);
memset(num,0,sizeof(num));
memset(tr,0,sizeof(tr));
p=0;
for(int i=1;i<=n;++i){
cin>>s;
add(s.length());
}
memset(f,0,sizeof(f));
f[l+1]=1;
for(int i=l;i>=1;--i){
que(i,l);
}
printf("Case %d: %d\n",cnt,f[1]);
}
return 0;
}