UVa 1401 Remember the Word

Trie+DP
트리백서의 문제 훈련.
그것은 이탈리아는 여러 가지로 구성된 작은 현이 있는 문자열이라고 말한다.
예컨대
abcd 
4
a
b
cd
ab
abcd=a+b+cd.abcd=ab+cd;
마지막 분에서 앞으로.dp[i]=dp[i]+dp[i+len[x]x는 입력할 때의 순서로 노드에 추가됩니다.i~strlen (S) 의 접두사입니다.S[1,2,3,…,i,…len]
Trie 트리를 구성할 때 노드에도 순서를 추가합니다.
마지막으로 검색할 때 몇 개의 문자열의 접두사를 찾아내고 이 접두사를 모두 합쳐라.

#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<stack>
#include<iostream>
#include<list>
#include<set>
#include<cmath>
#define INF 0x7fffffff
#define eps 1e-6
#define LL long long
using namespace std;
const int MOD=20071027;

struct Trie
{
    int word[4001*100][26];
    int ex[4001*100];
    int size;

    void clear()
    {
        memset(word[0],0,sizeof(word[0]));
        size=1;
        ex[0]=0;
    }

    int insert(char *s,int v)
    {
        int u=0,c;
        for(int i=0; s[i]!='\0'; i++)
        {
            int c=s[i]-'a';
            if(!word[u][c])
            {
                memset(word[size],0,sizeof(word[size]));
                ex[size]=0;
                word[u][c]=size++;
            }
            u=word[u][c];
        }
        ex[u]=v;
    }

    int search(char *s,int len,vector<int>& ans)
    {
        int u=0,c;
        for(int i=0; s[i]!='\0'&&i<len; i++)
        {
            c=s[i]-'a';
            if(!word[u][c])return 0;
            u=word[u][c];
            if(ex[u])
                ans.push_back(ex[u]);
        }
    }
} wo;

char str[300001];
int dp[300001];
int n;
int le[4001];

int main()
{
    int nn=1;
    while(scanf("%s",str)!=EOF)
    {
        scanf("%d",&n);
        wo.clear();
        memset(dp,0,sizeof(dp));
        char tmp[101];
        int len=strlen(str);

        for(int i=0; i<n; i++)
        {
            scanf("%s",tmp);
            le[i+1]=strlen(tmp);
            wo.insert(tmp,i+1);
        }
        dp[len]=1;
        for(int i=len-1; i>=0; i--)
        {
            vector<int>ans;
            wo.search(str+i,len-i,ans);
            for(int j=0; j<ans.size(); j++)
                dp[i]=(dp[i]+dp[i+le[ans[j]]])%MOD;
        }
        printf("Case %d: %d
",nn++,dp[0]);
    }
}

판권 성명: 본문 블로그 오리지널 문장.블로그는 동의 없이 전재할 수 없다.