思路

用trie树优化dp

设f[i]表示到第i个的方案数，则有\(f[i]=\sum_{x}f[i+len[x]]\)（x是s[i,n]的一个前缀），所以需要快速找出所有前缀，用Trie树即可

代码

#include <cstdio>

#include <algorithm>

#include <cstring>

using namespace std;

const int MOD = 20071027;

int dp[301000],Trie[400100][26],Nodecnt=1,root=1,isword[400100],S,len[400100];

char s[301000],w[4011][110];

void insert(char *s,int ln,int inq){

    int o=root;

    for(int i=0;i<ln;i++){

        if(!Trie[o][s[i]-'a'])

            Trie[o][s[i]-'a']=++Nodecnt;

        o=Trie[o][s[i]-'a'];

    }

    isword[o]=inq;

}

void query(char *s,int ln,int pos){

    int o=root;

    for(int i=0;i<ln&&o;i++){

        o=Trie[o][s[i]-'a'];

        if(isword[o])

            dp[pos]=(dp[pos]+dp[pos+len[isword[o]]])%MOD;

    }

}

void init(){

    Nodecnt=1;

    root=1;

    memset(Trie,0,sizeof(Trie));

    memset(isword,0,sizeof(isword));

    memset(dp,0,sizeof(dp));

}

int main(){

    // freopen("test.in","r",stdin);

    // freopen("test.out","w",stdout);

    int cnt=0;

    while(~scanf("%s",s+1)){

        ++cnt;

        init();

        scanf("%d",&S);

        for(int i=1;i<=S;i++){

            scanf("%s",w[i]+1);

            len[i]=strlen(w[i]+1);

            insert(w[i]+1,len[i],i);

        }

        int lens=strlen(s+1);

        dp[lens+1]=1;

        for(int i=lens;i>=1;i--){

            query(s+i,lens-i+1,i);

        }

        printf("Case %d: %d\n",cnt,dp[1]);

    }

    return 0;

}