UVA 1401：Remember the Word（字典树处理单词构成句子的方法数）

数据结构

题面链接

• 题意

给你一个字符串s再给你n个小串s1，问用这些小串构成这个大串有多少种不同的方法。对于输出答案mod上20071027。

• 样例

Sample Input
abcd // 大串s（长度小于 300 000）
4 //n（1 <= n <= 4000）
a
b
cd
ab //接下来的n个小串（长度都不超过100）
Sample Output
Case 1: 2

• 分析

用字典树建树，将所有的小串放到字典树里。
对长串的每一位循环。沿着树往下走直到走到不能与长串匹配为止。此时循环到长串的下一位，依次找下去。

• 代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=4e5+5;
const int mod=20071027;
int ch[maxn][30];//ch[i][j]表示在i节点标号为j的字母出现的节点位置
int isword[maxn];//标记是否是一个单词的结尾
int dp[maxn];
char s[maxn],s1[105];
int cnt=0;
void insert(char s[])//字典树
{
    int root=0;
    int l=strlen(s);
    for(int i=0;i<l;i++)
    {
        if(ch[root][s[i]-'a']==0)//该点还未出现过
        {
            ch[root][s[i]-'a']=++cnt;//建点
        }
        root=ch[root][s[i]-'a'];
    }
    isword[root]=1;//是一个单词的结尾
}
void f(int i)
{
    int temp=dp[i-1];
    int root=0;
    while(1)//每个节点能够往后延伸的地方
    {
        root=ch[root][s[i]-'a'];
        if(root==0)
            break;
        if(isword[root]==1)//到达某个单词的结尾
            dp[i]=(dp[i]+temp)%mod;
        i++;//看下一位是否能继续匹配
    }
}
int main()
{
    int t=0;
    while(~scanf("%s",s+1))
    {
        memset(ch,0,sizeof(ch));
        memset(dp,0,sizeof(dp));
        memset(isword,0,sizeof(isword));//清空不能忘！！
        int n;
        scanf("%d",&n);
        while(n--)
        {
            scanf("%s",s1);
            insert(s1);
        }
        int l=strlen(s+1);
        dp[0]=1;//这样才能往后累加啊
        for(int i=1;i<=l;i++)
        {
            if(dp[i-1])//说明之前是来到过这一位的。这里曾是某个单词的结尾。
                f(i);
        }
        printf("Case %d: %d\n",++t,dp[l]);
    }
    return 0;
}