学步园

本题很容易想到

状态转移方程dp（i）=sum（dp（j））； i为从位置i到S末尾的后缀，而i -> j-1 为在字典中存在的word；

直接枚举 i -> j-1 会超时； 用前缀数组优化；

#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int INF = -1;
const int TRU = 1;
const int MOD = 20071027;
struct Trie {

static const int maxnnode = 4000*90;
static const int sigma_size = 27;

int ch[maxnnode][sigma_size];
int val[maxnnode];
int sz;
Trie(){sz=1; memset(ch[0],0,sizeof(ch[0]));}
int idx(char c){return c-'a';}
void clear();
void insert(char* s);
bool count(char* s);
void Count(char* s,int st,int n,vector<int>& ans);
};
void Trie::clear(){
sz=1; memset(ch[0],0,sizeof(ch[0]));
}

void Trie::insert(char* s){
int u=0,n=strlen(s);
for(int i=0;i<n;i++){
int c=idx(s[i]);
if(!ch[u][c]){
memset(ch[sz],0,sizeof(ch[sz]));
val[sz]=INF;
ch[u][c]=sz++;
}
u=ch[u][c];
}
val[u]=TRU;
}

bool Trie::count(char* s){
int u=0,n=strlen(s);
for(int i=0;i<n;i++){
int c=idx(s[i]);
if(!ch[u][c]) return false;
u=ch[u][c];
}
if(val[u]==INF) return false;
return true;
}

void Trie::Count(char* s,int st,int n,vector<int>& ans){
int u=0;
for(int i=st;i<n;i++){
int c=idx(s[i]);
if(!ch[u][c]) { break;}
else {
if(val[ch[u][c]]==TRU) ans.push_back(i);
}
u=ch[u][c];
}
}
const int maxn = 300100;
char str[maxn],src[maxn];
int d[maxn],vv[maxn],len;
Trie vis;
int dp(int i){
if(vv[i]) return d[i];
vv[i]=1;
if(i==len) return d[i]=1;
vector<int> ans;
vis.Count(str,i,len,ans);
d[i]=0;
for(int j=0;j<ans.size();j++){
d[i]=(d[i]+dp(ans[j]+1))%MOD;
}
return d[i];
}
int main()
{
    int kase=1;
    while(gets(str)){
      int n;
      scanf("%d",&n);
      vis.clear();
      gets(src);
      for(int i=0;i<n;i++){
      gets(src);
      vis.insert(src);
      }
      len=strlen(str);
      memset(vv,0,sizeof(vv));
      printf("Case %d: %d\n",kase++,dp(0));
    }
    return 0;
}