UVALive - 3942 （DP + Trie树）

给出一个长度不超过300000的字符串 S，然后给出 n 个长度不超过100的字符串。

如果字符串可以多次使用，用这 n 个字符串组成 S 的方法数是多少？

比如样例中，abcd = a + b + cd = ab + cd

dp[i] 表示用这n个字符串构成，S中从 i ~ len之间的字母构成的子串，的可分解方案数。

如果存在一个位置 x >= i，且 i~x 之间的字母是一个单词，那么dp[i] = ∑ ( dp[x] )

但是如果暴力枚举 i ~ x是不是一个单词，必然会TLE。这时我们就需要 Trie 树优化这个DP。

#include <iostream>

#include <cstdlib>

#include <cstdio>

#include <cmath>

#include <cstring>

using namespace std;

#define maxn 400000 + 100

#define sigma_size 27

#define LL long long

#define MOD 20071027

int tot = ;

int trie[maxn][sigma_size], sum[maxn], dp[maxn];

void insert(char s[])

{

        int root = ;

        for (int i = ; s[i]; i++)

        {

                int id = s[i]-'a';

                if (!trie[root][id])

                {

                        sum[++tot] = ;

                        trie[root][id] = tot;

                }

                root = trie[root][id];

        }

        sum[root] = ;

}

void found(char s[], int k)

{

        int root = ;

        for (int i = k; s[i]; i++)

        {

                int id = s[i]-'a';

                if (!trie[root][id])

                        return;

                root = trie[root][id];

                if (sum[root])

                        dp[k] = (dp[k]+dp[i+])%MOD;

        }

}

int main()

{

        char s[maxn];

        int len, ca = ;

        while(scanf("%s", s) != EOF)

        {

                char t[maxn];

                int n;

                scanf("%d", &n);

                memset(trie, , sizeof(trie));

                memset(sum, , sizeof(sum));

                for (int i = ; i <= n; i++)

                {

                        scanf("%s", t);

                        insert(t);

                }

                memset(dp, , sizeof(dp));

                len = strlen(s);

                dp[len] = ;

                for (int i = len-; i >= ; i--)

                        found(s, i);

                printf("Case %d: %d\n", ++ca, dp[]);

        }

}

巴特西

UVALive - 3942 （DP + Trie树）

最新文章

热门文章