vvalive 3942 Remember the Word(사전 트리 + DP)

S개의 다른 단어와 긴 문자열을 주고 몇 개의 단어로 분해하는 방법이 몇 가지냐고 묻는다(단어 중복 사용 가능)
해법:
dp[i]를 설정하면 i로 시작하는 문자열의 분해 방법을 나타냅니다.상태 이동 방정식: dp[i]=sum(dp[i+len(x)]), x는 S[i...L]의 접두사입니다.
단어 하나하나를 사전 트리에 삽입한 다음 긴 문자열 S의 접두사 s[i...L]를 고려하여 접두사 x가 사전 트리에 나타나는지 확인하고 나타날 때마다 dp[i]에 dp[i+len(x)]를 누적하면 된다.
총결산점의 수량 크기와 dp의 초기화에 주의하세요.

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
#define maxn 300005
#define maxm 26
#define mod 20071027
int tree[maxn][maxm],val[maxn],cnt;//Trie 、    、    
int dp[300005];
void init()
{
    cnt=1;
    memset(tree[0],0,sizeof(tree[0]));
    memset(dp,0,sizeof(dp));
}

inline void Insert(char *s,int v)
{
    int id=0,l=strlen(s);
    for(int i=0; i<l; ++i)
    {
        int c=s[i]-'a';
        if(!tree[id][c])
        {
            memset(tree[cnt],0,sizeof(tree[cnt]));
            tree[id][c]=cnt++;
            val[cnt]=0;
        }
        id=tree[id][c];
    }
    val[id]=v;//                    v
}


inline void querry(char *s,int l,int pos)
{
    int id=0;
    for(int i=pos; i<l; ++i)
    {
        int c=s[i]-'a';
        if(!tree[id][c]) return;
        id=tree[id][c];
        if(val[id]) dp[pos]=(dp[pos]+dp[i+1])%mod;
    }
}

char str[300005],w[105];
int main()
{
    int n,ca=1;
    while(~scanf("%s",str))
    {
        scanf("%d",&n);
        init();
        for(int i=0; i<n; ++i)
        {
            scanf("%s",w);
            Insert(w,1);
        }
        int l=strlen(str);
        dp[l]=1;
        for(int i=l-1;i>=0;--i) querry(str,l,i);
        printf("Case %d: %d
",ca++,dp[0]);
    }
    return 0;
}