LA3942 Remember the Word(Trie+DP)
来源：程序员人生 发布时间：2014-10-11 08:00:01 阅读次数：2707次
Trie图的简单应用。这题关键是想出递推式。令d(i)表示从字符i开始的字符串，d(i)=sum{d(i+len(x))},x是s[i...L]的前缀。然后把所有可分解成的单词构造成一颗Trie树，再让母串在上面跑，d[0]即是方案总数。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define mod 20071027
#define M 400005
using namespace std;
int n,top,len;
int tree[M][27];
char S[M];
char p[105];
int val[M];
int d[M];
void init()
{
top=1;
memset(tree,0,sizeof(tree));
memset(d,0,sizeof(d));
}
int idx(char c)
{
return c-'a';
}
void insert(char *s)
{
int Len=strlen(s);
int u=0;
for(int i=0;i<Len;i++)
{
int c=idx(s[i]);
if(!tree[u][c])
{
val[top]=0;
tree[u][c]=top++;
}
u=tree[u][c];
}
val[u]=1;
}
int query(char *s,int start)
{
int count=0;
int u=0;
for(int i=start;i<len;i++)
{
int c=idx(s[i]);
u=tree[u][c];
if(!u) return count;
if(val[u])
{
count+=d[i+1];
count%=mod;
}
}
return count;
}
int main()
{
int t=1;
//freopen("d: est.txt","r",stdin);
while(scanf("%s",S)!=EOF)
{
scanf("%d",&n);
init();
for(int i=0;i<n;i++)
{
scanf("%s",p);
insert(p);
}
len=strlen(S);
d[len]=1;
for(int i=1;i<=len;i++)
{
d[len-i]=query(S,len-i);
}
cout<<"Case "<<t++<<": "<<d[0]<<endl;
}
return 0;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
