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)


相关推荐

  • 51单片机智能小车循迹PPT_基于51单片机的智能小车

    51单片机智能小车循迹PPT_基于51单片机的智能小车第3章系统硬件电路设计3.1总体设计智能小车采用两个前轮和一个万向轮的方式,在前轮的左右两端各安装一个电机驱动,利用电机驱动芯片L293D来控制两个前轮的左右转向和停止,后轮是一个万向轮,有支撑和转向的作用。在车体底盘的前端装有4个红外光电传感器,用以实现路迹检测和避障功能。小在小车的车头还装置有超声波探测模块HC-SR04,当前方检测到障碍物时,小车能够做出相应的反应。总体设计框图如图3-1。…

    2022年10月17日
  • Qt面试题(二)

    Qt面试题(二)QT理论试题1以下关于QT的描述正确的是a.是一个不跨平台的C++图形用户界面b.由挪威TrollTech公司出品c.只支持Unix、Linuxd.QTAPI和开发工具对所支持的平台是不一致的2以下关于QT的描述不正确的是a.QT支持2D图形渲染b.QT支持3D图形渲染c.QT支持OpenGL d.QT不支持XML…

  • VS2013序列号_visual studio2010激活码

    VS2013序列号_visual studio2010激活码VS2008序列号/注册码(各种版本都有)2009-08-2123:18   –VS2008.NET简体中文版序列号1.VisualStudio2008ProfessionalEdition:XMQ2Y-4T3V6-XJ48Y-D3K2V-6C4WT2.VisualStudio2008TeamTestLoadAgent:WPX3J-BXC3W

  • rpm 安装及更新

    rpm 安装及更新安装rpmsudorpm-ivh/Users/aaa.bbb/rpmbuild/RPMS/x86_64/worker-0.0.1-1.x86_64.rpm–force–prefix=/home/chroot/最后prefix是指定安装路径,如果不指定,就是在根目录/rpm-qa|grept-server…

  • pycharm安装后无法运行_pycharm代码运行不了

    pycharm安装后无法运行_pycharm代码运行不了问题:pycharm安装后不能执行python脚本的问题原因:pycharm没有设置解析器解决方法:打开pycharm->File->Settings->ProjectInterpreter->设置未你的python路径,我的是:C:\Python27\python.exe,你们根据各自python安装路径修改一下即可

发表回复

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

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