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