思路

用trie树优化dp

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

代码

#include 
    
     #include 
     
      #include 
      
       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
       
        =1;i--){            query(s+i,lens-i+1,i);        }        printf("Case %d: %d\n",cnt,dp[1]);    }    return 0;}