UVALive 3942 Remember the Word 字典树+dp

/**
题目：UVALive 3942 Remember the Word 
链接：https://vjudge.net/problem/UVALive-3942
题意：给定一个字符串(长度最多3e5)和m个单词(每个单词长度最多100)。单词都是不同的。该字符串可以由若干个单词组成，问最多有多少种组合方式。

思路：字典树+dp
用字典树处理好m个单词，定义dp[i]表示从i开始的字符串可以由单词组成的方式数。
那么dp[i] += dp[i+j]; j表示某个单词和字符串的[i,i+j-1]匹配。

*/

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
using namespace std;
typedef pair<int,int> P;
typedef long long LL;
const int mod = 20071027;
const int INF = 0x3f3f3f3f;
const int maxnode = 4e5+10;///最多可能有多少个节点
const int maxn = 3e5+100;
const int sigma_size = 26;///26个字母
int dp[maxn];
char s[maxn], ss[maxn];安全1
int ch[maxnode][sigma_size];///由于很大，所以结构体内部放不下。要放在外面。
struct Trie{
    int val[maxnode];
    int sz;
    int idx(char c){return c-'a';}

    void insert(char *s,int v)
    {
        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] = 0;
                ch[u][c] = sz++;
            }
            u = ch[u][c];
        }
        val[u] = v;
    }

    void query(int sta,int off)
    {
        int u = 0;
        int c = idx(s[sta]);
        while(s[sta]!=''&&ch[u][c]){
            if(val[ch[u][c]]){
                dp[sta-off] = (dp[sta-off]+dp[sta+1])%mod;
            }
            u = ch[u][c];
            c = idx(s[++sta]);
            off++;
        }
    }
};

int main()
{
    int cas = 1;
    int n;
    Trie trie;
    while(scanf("%s",s)==1)
    {
        scanf("%d",&n);
        trie.sz = 1;
        memset(ch[0], 0, sizeof ch[0]);
        for(int i = 0; i < n; i++){
            scanf("%s",ss);
            trie.insert(ss,1);
        }
        int m = strlen(s);
        memset(dp, 0, sizeof dp);
        dp[m] = 1;
        for(int i = m-1; i>=0; i--){
            trie.query(i,0);
        }
        printf("Case %d: %d
",cas++,dp[0]);
    }
    return 0;
}