uva 1401 dp+Trie

uva 1401 dp+Trie

大家好,又见面了,我是全栈君,今天给大家准备了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;
}


版权声明:本文博主原创文章。博客,未经同意不得转载。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116891.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • “007~ASP 0104~不允许操作”错误的解决方法(图解)

    “007~ASP 0104~不允许操作”错误的解决方法(图解)

    2021年11月17日
  • 大数据时代来临,数据应用随处可见吗_随着大数据时代的来临

    大数据时代来临,数据应用随处可见吗_随着大数据时代的来临序:大数据之所以可能成为一个时代,在很多程度上是因为这是一个可以由社会各界广泛参与,八面出击,处处结果的社会运动,而不仅仅是少数专家学者的研究对象。数据产生于各行各业,这场变革也必将影响到各行各业,因此,机遇也蕴含于各行各业。致力于IT创业的人们紧紧盯着这个市场,洞察着每一个机遇。数据对于科学进步有推动的作用,而海量数据对数据的分析既带来了机遇,也构成了新的挑战。随着大数据的迅速发展,许多企业开始…

  • js倒计时代码最简单的(js倒计时10秒代码)

    第一种:精确到秒的javascript倒计时代码HTML代码:离2010年还有:startclock()vartimerID=null;vartimerRunning=false;functionshowtime(){Today=newDate();varNowHour=T

  • qt中QHBoxLayout或QVBoxLayout布局内控件的动态生成与显示[通俗易懂]

    qt中QHBoxLayout或QVBoxLayout布局内控件的动态生成与显示[通俗易懂]恢复内容开始qt中QHBoxLayout或QVBoxLayout布局内控件的动态生成与显示打个比方,我现在写个小例子,这个小例子是这样的,整个界面分为俩个部分,分为上半部分和下半部分,上半部分为5

  • wpf wrapPanel居中并从左到右排列

    wpf wrapPanel居中并从左到右排列publicclassAlignableWrapPanel:Panel{///<summary>///注册新的属性HorizontalContentAlignment///</summary>publicHorizontalAlignmentHorizontalContentAlignment{get{return(Horizont.

  • 基于单片机的八路抢答器设计论文_抢答器的程序流程图

    基于单片机的八路抢答器设计论文_抢答器的程序流程图文末下载完整资料1.1八路扫描式抢答器的概述  本文介绍的八路数显抢答器具有电路简单、成本较低、操作方便、灵敏可靠等优点,经使用效果良好,具有较高的推广价值。无线遥控抢答器,它由8个发射器和1个接收器组成,可用于8组或8组以下的智力竞赛中。比赛前,将参赛组从0至7编号,每组发给对应的一个发射器。将接收器放于各组中央或前方。主持人按一下启动键后,抢答开始。此后,哪一组最先按下发射器上的抢答键,接收器就立即显示该组的组号并锁定,同时发出3次清脆的“叮咚”声。以后,按下任何一路抢答键均不起反映。只有主

    2022年10月20日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号