LIsa

就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: %dn",cnt,f[1]);
    }
    return 0;
}