当前位置:网站首页>uva 1401 dp+Trie
uva 1401 dp+Trie
2022-07-07 01:42:00 【Full stack programmer webmaster】
Hello everyone , I meet you again , I'm the king of the whole stack , I've prepared for you today Idea Registration code .
http://uva.onlinejudge.org/index.php?
option=com_onlinejudge&Itemid=8&page=show_problem&category=&problem=4147
The question : Given a string , And some words , There are several ways to use words to form a string
First I was dp There was a problem with the equation. I don't know how to change it. It got stuck for a long time , Then the array is opened too small and always RE
trie Array size = The number of words * Word length
dp[i] For str[i] Beginning with suffix ans.dp[i]=segma(dp[k]), among k Express str[i…k-1] It's a word . hypothesis k=len, that 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] Express dp[i..len-1] It's a word , At this time, the number of cutting types is not added
{
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 For the length
{
int rt,nxt;
for(rt=0;*s;rt=nxt,++s,Rank++)
{
nxt=tree[rt][*s-tb];
if(0 == nxt)//nxt!=0 When there is a public prefix . It has been done before , Just continue to jump he Insert her, To h,e All are nxt!=0 Don't insert
{
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;
}
Copyright notice : This article is the original article of the blogger . Blog , Do not reprint without permission .
Publisher : Full stack programmer stack length , Reprint please indicate the source :https://javaforall.cn/116891.html Link to the original text :https://javaforall.cn
边栏推荐
- Taro applet enables wxml code compression
- Google发布安全更新,修复Chrome中已被利用的0 day
- 使用nodejs完成判断哪些项目打包+发版
- 修改px4飞控的系统时间
- Instructions for using the domain analysis tool bloodhound
- POJ 3177 Redundant Paths POJ 3352 Road Construction(双连接)
- [advanced C language] 8 written questions of pointer
- JS reverse -- ob confusion and accelerated music that poked the [hornet's nest]
- C语言实例_3
- AcWing 1142. 繁忙的都市 题解(最小生成树)
猜你喜欢
新工作感悟~辞旧迎新~
AcWing 361. 观光奶牛 题解(spfa求正环)
AcWing 345. Cattle station solution (nature and multiplication of Floyd)
爬虫实战(六):爬笔趣阁小说
Right mouse button customization
AcWing 345. 牛站 题解(floyd的性质、倍增)
Dark horse notes - exception handling
[advanced C language] 8 written questions of pointer
Reptile practice (VI): novel of climbing pen interesting Pavilion
The difference between Tansig and logsig. Why does BP like to use Tansig
随机推荐
Byte P7 professional level explanation: common tools and test methods for interface testing, Freeman
Appium automation test foundation uiautomatorviewer positioning tool
POJ 3177 Redundant Paths POJ 3352 Road Construction(双连接)
AcWing 904. Wormhole solution (SPFA for negative rings)
百度飞将BMN时序动作定位框架 | 数据准备与训练指南 (上)
设置Wordpress伪静态连接(无宝塔)
使用nodejs完成判断哪些项目打包+发版
ZOJ problem set – 2563 long dominoes [e.g. pressure DP]
Clickhouse fields are grouped and aggregated, and SQL is queried according to the granularity of any time period
交叉验证如何防止过拟合
Reptile practice (VI): novel of climbing pen interesting Pavilion
AcWing 1141. LAN problem solving (kruskalkruskal finding the minimum spanning tree)
Comparison of picture beds of free white whoring
字符串转成日期对象
C语言关于链表的代码看不懂?一篇文章让你拿捏二级指针并深入理解函数参数列表中传参的多种形式
tansig和logsig的差异,为什么BP喜欢用tansig
增加 pdf 标题浮窗
C语言【23道】经典面试题【下】
C语言实例_4
When grep looks for a process, it ignores the grep process itself