UVALive - 3942 Remember the Word(trie + dp) - dblank

UVALive - 3942 Remember the Word(trie + dp)

题目链接:http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=22109;

思路:dp[i]表示原串从i开始的后段子串的方案数,从后往前dp,然后dp[i] = sum(dp[i + len(x)],这里的x是给出单词并且是这后段的前缀串。如果直接枚举的话会超时,先把单词全部加到字典树上面然后在字典树上面查找就可以了。我是用指针的写法,记住每组数据输出后一定要初始化字典树!

#include<iostream>  
#include<cstdio>  
#include<algorithm>  
#include<map>  
#include<cstring>  
#include<map>  
#include<set>  
#include<queue>  
#include<stack>  
#include<cmath>  
using namespace std;  
const double eps = 1e-10;  
const int inf = 0x7fffffff, N = 3e5 + 10, mo = 20071027;  
typedef long long ll;  
using namespace std;  
struct trie  
{  
    int data;  
    trie *Next[26];  
    trie()  
    {  
        data = 0;  
        memset(Next, 0, sizeof(Next));  
    }  
};  
char s[N], x[110];  
int dp[N], len;  
trie *root;  
void trie_insert(char *str)  
{  
    trie *p = root;  
    for(int i = 0; str[i]; i++)  
    {  
        int ch = str[i] - 'a';  
        if(p->Next[ch] == NULL) p->Next[ch] = new trie;  
        p = p->Next[ch];  
    }  
    p->data++;  
}  
int trie_find(char *str, int sta)  
{  
    int cnt = 0;  
    trie *p = root;  
    for(int i = 0; str[i]; i++)  
    {  
        int ch = str[i] - 'a';  
        p = p->Next[ch];  
        if(p == NULL) return cnt;  
        if(p->data) cnt = (cnt + dp[i + sta + 1])%mo;  
    }  
    return cnt;  
}  
void del(trie * p)  
{  
    if(p == NULL)  
        return ;  
    else  
    {  
        for(int i = 0; i<26; i++)  
            del(p->Next[i]);  
    }  
    delete p;  
}  
int main()  
{  
    int n, cas = 1;  
  
    while(~scanf("%s", s))  
    {  
        root = new trie;  
        scanf("%d", &n);  
        memset(dp, 0, sizeof(dp));  
        len = strlen(s);  
        dp[len] = 1;  
        for(int i = 1; i<=n; i++)  
        {  
            scanf("%s",x);  
            trie_insert(x);  
        }  
        for(int i = len - 1; i>=0; i--)  
            dp[i] = trie_find(s+i, i);  
        printf("Case %d: %d\n", cas++, dp[0]);  
        del(root);  
    }  
    return 0;  
}  

 

相关文章

发表新评论