大家好，又见面了，我是全栈君，今天给大家准备了Idea注册码。
http://uva.onlinejudge.org/index.php?
option=com_onlinejudge&Itemid=8&page=show_problem&category=&problem=4147
题意：给定一个字符串，以及若干单词，求有几种方式能用单词组成字符串
我先是dp方程推得有问题不知怎么改动搞得卡了非常久，然后就是数组开得太小一直RE
trie数组大小=单词个数*单词长度
dp[i]为以str[i]开头的后缀的ans。dp[i]=segma(dp[k]),当中k表示str[i…k-1]是一个单词。假设k=len,那么dp[i]++；
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
#define ll long long
const int N =4000*100+100;
const int MOD =20071027;
char str[300019],pat[115];
ll dp[300019];
const int tk=26,tb='a';
int top,tree[N][tk+1],len;
void init()
{
top=1;
memset(tree[0],0,sizeof(tree[0]));
}
int sear(char*s,int i)
{
int cnt=0;
ll ans=0;
for(int rt=0;rt=tree[rt][*s-tb] ;++s)
{
if(*(s)==0)break;
cnt++;
if(tree[rt][tk])//cnt!=tree[rt][tk]表示dp[i..len-1]是一个单词，此时没有添加切割的种数
{
if(*(s+1)==0)ans++;
ans=(ans+dp[i+cnt])%MOD;
//////////////////////
//printf("rt=%d s=%s i=%d cnt=%d dp=%lld\n",rt,str+i+cnt,i,cnt,dp[i]);
//////////////////////
}
}
return ans;
}
void Insert(char*s, int Rank=0)//Rank为长度
{
int rt,nxt;
for(rt=0;*s;rt=nxt,++s,Rank++)
{
nxt=tree[rt][*s-tb];
if(0 == nxt)//nxt!=0的时候就是有公共前缀了。已经在之前做过了，仅仅需继续跳转即可he中插入her,到h,e都是nxt!=0不用插入
{
tree[rt][*s-tb]=nxt=top;
memset(tree[top],0,sizeof(tree[top]));
top++;
}
}
tree[rt][tk]=Rank;
}
int main()
{
//freopen("uva1401.txt","r",stdin);
int n,ncase=1,pos;
while(scanf("%s",str)!=EOF)
{
init();
pos=0;
len=strlen(str);
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%s",pat);
Insert(pat);
}
dp[len]=0;
for(int i=len-1;i>=0;i--)
{
dp[i]=0;
dp[i]=sear(str+i,i);
}
printf("Case %d: %lld\n",ncase++,dp[0]);
}
return 0;
}
版权声明：本文博主原创文章。博客，未经同意不得转载。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/116891.html原文链接：https://javaforall.net
