LA3942 Remember the Word

题目链接：https://vjudge.net/problem/UVALive-3942

本篇是刘汝佳《算法竞赛入门经典——训练指南》的读书笔记（复述），详见原书 \(P209\) .

解题思路：

　　先用字典树维护字典中所有的单词。

　　定义 \(f(x)\) 为以长字符串中第 \(x\) 个字符开始的字符串的分解方案数，则 \(f(x) = sum{f(x+len(i))}\) ，其中 \(i\) 是该字符串的所有前缀。

　　用一种类似 \(DFS\) 的方式解决这个问题。

　　注意：书中的模数写错了。

AC代码：

 #include <bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const ll mod = ;

 const int maxn = +;

 char inp[maxn];

 struct Trie{

     int ch[][];

     int val[];

     int sz;

     void inserts(char *s,int v){

         int u=,n=strlen(s);

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

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

             if(!ch[u][c]){

                 memset(ch[sz],,sizeof(ch[sz]));

                 val[sz]=;

                 ch[u][c]=sz++;

             }

             u=ch[u][c];

         }

         val[u]=v;

     }

 };

 Trie tree;

 ll f[maxn];

 ll solve(int head,int tail){

     if(f[head]!=-) return f[head];

     int now=;

     ll ret=;

     for(int i=head;i<tail;i++){

         int c=inp[i]-'a';

         int Next=tree.ch[now][c];

         if(Next==){

             f[head]=ret;

             return ret;

         }

         if(tree.val[Next])

             ret=(ret+solve(i+,tail))%mod;

         now=Next;

     }

     f[head]=ret;

     return ret;

 }

 int main(){

     char word[];

     int kase=;

     while(scanf("%s",inp)==){

         int S;

         memset(f,-,sizeof(f));

         tree.sz=;

         memset(tree.ch[],,sizeof(tree.ch[]));

         scanf("%d",&S);

         while(S--){

             scanf("%s",word);

             tree.inserts(word,);

         }

         int tail=strlen(inp);

         f[tail]=;

         printf("Case %d: %lld\n",kase++,solve(,tail));

     }

     return ;

 }

巴特西

LA3942 Remember the Word

最新文章

热门文章