uva 1401 dp+Trie

2158 ワード

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=&problem=4147
題意:1つの文字列を与えて、およびいくつかの単語、いくつかの方式を求めて単語で文字列を構成することができます 
私はまず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
",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
",ncase++,dp[0]); } return 0; }