UVa: 1401 Remember the Word(사전 트리)

사전 트리, 처음 씁니다.아직 미루어야 한다.
dp[i]=sum｛dp[i+len(x)]｝x는str[i...L]의 접두사 길이입니다.
소박한 생각은 모든 x를 매거한 다음에str[i...L]의 접두사인지 판단하는 것이다. 이것은 시간의 복잡도가 약 30000*4000*와 비교되는 시간으로 시간을 초과할 수 있다.
tire를 이용하여 불필요한 비교를 줄여서 모든 x를 신속하게 찾을 수 있다. 즉, 매번 찾은 것은str[i...L]의 접두사이다. 이렇게 하면 대부분이 30000*100이다.
사전 트리 정보.수조ch[i][j]로 저장된 것은 i뿌리 문자로 j의 결점 번호이고val[u]로 저장된 것은 u번째 결점의 추가 정보입니다.이 문제에서 val[]이 0이 아닌 것은 어떤 단어의 끝을 나타낸다.
sz가 표시할 때 결점 개수는 나무를 짓는 과정에서 이 값이 커진다. 그리고 나무를 짓기 전에ch【】,val【】와 대응하는 결점은 모두 비워야 한다.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
#define ll long long
#define INF 200000000
#define MOD 20071027
#define MAXN 5005
using namespace std;
int dp[300005];
struct Tire
{
    int ch[4005*100][26],val[4005*100];
    int sz;
    int idx(char c)
    {
        return c-'a';
    }
    void Reset()
    {
        sz=1;
        memset(ch,0,sizeof(ch));
        memset(val,0,sizeof(val));
    }
    void Insert(char *str,int v)
    {
        int u=0;
        for(int i=0; str[i]; ++i)
        {
            int c=idx(str[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 solve(int x,char *str)
    {
        for(int i=x,u=0; str[i]; ++i)
        {
            int c=idx(str[i]);
            if(!ch[u][c]) return ;
            u=ch[u][c];
            if(val[u])  dp[x]=(dp[x]+dp[i+1])%MOD;
        }
    }
};
char str[300005],word[105];
Tire tree;
int main()
{
    int kase=0;
    while(scanf("%s",str)!=EOF)
    {
        int n;
        tree.Reset();
        memset(dp,0,sizeof(dp));
        scanf("%d",&n);
        for(int i=0; i<n; ++i)
        {
            scanf("%s",word);
            tree.Insert(word,1);
        }
        dp[strlen(str)]=1;
        for(int i=strlen(str)-1; i>=0; --i)
            tree.solve(i,str);
        printf("Case %d: %d
",++kase,dp[0]);
    }

    return 0;
}