当前位置:网站首页>uva 1401 dp+Trie
uva 1401 dp+Trie
2022-07-06 17:56:00 【全栈程序员站长】
大家好,又见面了,我是全栈君,今天给大家准备了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.cn/116891.html原文链接:https://javaforall.cn
边栏推荐
- NEON优化:关于交叉存取与反向交叉存取
- Yunna | work order management measures, how to carry out work order management
- [case sharing] basic function configuration of network loop detection
- [Niuke] [noip2015] jumping stone
- 数据手册中的词汇
- Instructions for using the domain analysis tool bloodhound
- [JS] obtain the N days before and after the current time or the n months before and after the current time (hour, minute, second, year, month, day)
- Installation and testing of pyflink
- 今日问题-2022/7/4 lambda体中修改String引用类型变量
- AI 从代码中自动生成注释文档
猜你喜欢
1123. 最深叶节点的最近公共祖先
Segmenttree
Wood extraction in Halcon
[100 cases of JVM tuning practice] 05 - Method area tuning practice (Part 2)
golang中的Mutex原理解析
Body mass index program, entry to write dead applet project
力扣1037. 有效的回旋镖
JTAG debugging experience of arm bare board debugging
ARM裸板调试之JTAG原理
[Niuke] b-complete square
随机推荐
Realize incremental data synchronization between MySQL and ES
搭建【Redis in CentOS7.x】
Implementation principle of waitgroup in golang
Asset security issues or constraints on the development of the encryption industry, risk control + compliance has become the key to breaking the platform
How to prevent overfitting in cross validation
微信公众号发送模板消息
Neon Optimization: summary of performance optimization experience
The cost of returning tables in MySQL
Case development of landlord fighting game
交叉验证如何防止过拟合
Do you understand this patch of the interface control devaxpress WinForms skin editor?
第三方跳转网站 出现 405 Method Not Allowed
Spark TPCDS Data Gen
Dark horse notes - exception handling
Dark horse notes - create immutable sets and streams
NEON优化:关于交叉存取与反向交叉存取
Typical problems of subnet division and super network construction
golang中的Mutex原理解析
【C语言进阶篇】指针的8道笔试题
LeetCode:1175. 质数排列