UVALive 3942 Remember The Word （Tire）

状态是DAG，因此方案用dp统计,dp[i] = sum(dp[i+len(x)])，x是以i开头的前缀且是单词，关键在于快速判断一个前缀是不是单词，可用Trie。

每一次转移的复杂度是O(maxlen)，maxlen是单词的最长长度。

#include<bits/stdc++.h>
using namespace std;

const int maxn = 4005*100//4000*98+26*26+26+1
,sigma_size = 26;


int ch[maxn][sigma_size];
bool vis[maxn];
int nd_cnt;

const int LEN = 3e5+5, mod = 20071027;
char str[LEN];
int d[LEN];

void init()
{
    nd_cnt = 1; memset(ch[0],0,sizeof(ch[0]));
}

void add(char *s)
{
    int u = 0;
    int n = strlen(s);
    for(int i = 0; i < n; i++){
        int c = word[i]-'a';
        if(!ch[u][c]){
            memset(ch[nd_cnt],0,sizeof(ch[nd_cnt]));
            vis[nd_cnt] = false;
            ch[u][c] = nd_cnt++;
        }
        u = ch[u][c];
    }
    vis[u] = true;
}

int main()
{
    //freopen("in.txt","r",stdin);
    char word[120];
    int kas = 0;
    while(gets(str)){
        init();
        int S; scanf("%d
",&S);
        while(S--){
            gets(word);
            add(word);
        }
        int n = strlen(str);
        d[n] = 1;
        for(int cur = n-1; cur >= 0; cur--){
            int u = 0; d[cur] = 0;
            for(int i = cur; i < n; i++){
                int c = str[i]-'a';
                if(!ch[u][c]) break;
                u = ch[u][c];
                if(vis[u]) d[cur] += d[i+1];
            }
            d[cur] %= mod;
        }
        printf("Case %d: %d
",++kas,d[0]);
    }
    return 0;
}