uva 1401 dp+Trie

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;
}

Copy

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