[LA 3942] Remember the Word

Link:

Solution:

感觉自己字符串不太行啊，要加练一些蓝书上的水题了……

$Trie$+$dp$

转移方程：$dp[i]=sum\{ dp[i+len(x)+1]\} (x为从第i位开始的字符串的前缀)$

计算一个字符串前缀的多模式匹配在$Trie$树上跑一遍就行啦！

Code:

#include <bits/stdc++.h>

using namespace std;

const int MAXN=4e5+,MOD=;

bool vis[MAXN];

char s[MAXN],tmp[MAXN];

int T,n,ch[MAXN][],dp[MAXN],l,len,cnt=,rt=;

int main()

{

    while(~scanf("%s",s+))

    {

        memset(ch,,sizeof(ch));memset(dp,,sizeof(dp));

        memset(vis,false,sizeof(vis));

        T++;len=strlen(s+);

        scanf("%d",&n);cnt=;

        for(int i=;i<=n;i++)

        {

            scanf("%s",tmp+);l=strlen(tmp+);

            int cur=rt;

            for(int j=;j<=l;j++)

            {

                if(!ch[cur][tmp[j]-'a'])

                    ch[cur][tmp[j]-'a']=++cnt;

                cur=ch[cur][tmp[j]-'a'];

            }

            vis[cur]=true;

        }

        dp[len+]=;

        for(int i=len;i>=;i--)

        {

            int cur=rt;

            for(int j=i;j<=len;j++)

            {

                if(!ch[cur][s[j]-'a']) break;

                cur=ch[cur][s[j]-'a'];

                if(vis[cur]) (dp[i]+=dp[j+])%=MOD;

            }

        }

        printf("Case %d: %d\n",T,dp[]);

    }

    return ;

}

巴特西

[LA 3942] Remember the Word

Link:

Solution:

Code:

最新文章

热门文章