Separate String

时间限制: 1 Sec 内存限制: 128 MB
提交: 50 解决: 16

题目描述

You are given a string t and a set S of N different strings. You need to separate t such that each part is included in S.

For example, the following 4 separation methods satisfy the condition when t=abab and S={a,ab,b}.

a,b,a,b
a,b,ab
ab,a,b
ab,ab
Your task is to count the number of ways to separate t. Because the result can be large, you should output the remainder divided by 1,000,000,007.

输入

The input consists of a single test case formatted as follows.

N
s1
:
sN
t
The first line consists of an integer N (1≤N≤100,000) which is the number of the elements of S. The following N lines consist of N distinct strings separated by line breaks. The i-th string si represents the i-th element of S. si consists of lowercase letters and the length is between 1 and 100,000, inclusive. The summation of length of si (1≤i≤N) is at most 200,000. The next line consists of a string t which consists of lowercase letters and represents the string to be separated and the length is between 1 and 100,000, inclusive.

输出

Calculate the number of ways to separate t and print the remainder divided by 1,000,000,007.

样例输入

3
a
b
ab
abab

样例输出

4

题解：在kuangbin的板子当中增加ln(以此为结尾的字符串的长度)，true_nex(也可以叫做true_fail，用于表示真正有效的fail值，即存在以此为结尾的字符串)数组；
true_nex数组层层计算即可，因为上层的true_nex肯定已被正确计算。然后在query函数里面跑一个简单的DP即可。

AC代码：

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 typedef long long ll;
  4 const ll mod=1e9+7;
  5 const int maxn=1e6+50;
  6 ll dp[maxn];
  7 struct Trie
  8 {
  9     int nxt[200010][26],fail[200010],endd[200010],ln[200010],true_nex[200010];
 10     int root,L;
 11     int newnode(){
 12         for(int i=0;i<26;i++){
 13             nxt[L][i]=-1;
 14         }
 15         true_nex[L]=0;
 16         ln[L]=0;
 17         endd[L++]=0;
 18         return L-1;
 19     }
 20     void init(){
 21         L=0;
 22         root=newnode();
 23     }
 24     void insert(char buf[])
 25     {
 26         int len=strlen(buf);
 27         int now=root;
 28         for(int i=0;i<len;i++){
 29             if(nxt[now][buf[i]-'a']==-1){
 30                 nxt[now][buf[i]-'a']=newnode();
 31                 ln[nxt[now][buf[i]-'a']]=ln[now]+1;
 32             }
 33             now=nxt[now][buf[i]-'a'];
 34         }
 35         endd[now]++;
 36     }
 37     void build()
 38     {
 39         queue<int> Q;
 40         fail[root]=root;true_nex[root]=root;
 41         for(int i=0;i<26;i++){
 42             if(nxt[root][i]==-1){
 43                 nxt[root][i]=root;
 44             }
 45             else{
 46                 fail[nxt[root][i]]=root;
 47                 true_nex[nxt[root][i]]=root;/**/
 48                 Q.push(nxt[root][i]);
 49             }
 50         }
 51         while(!Q.empty())
 52         {
 53             int now=Q.front();
 54             Q.pop();
 55             for(int i=0;i<26;i++)
 56             {
 57                 if(nxt[now][i]==-1){
 58                     nxt[now][i]=nxt[fail[now]][i];
 59                 }
 60                 else{
 61                     fail[nxt[now][i]]=nxt[fail[now]][i];
 62                     if(endd[nxt[fail[now]][i]]>0) true_nex[nxt[now][i]]=nxt[fail[now]][i];/**/
 63                     else true_nex[nxt[now][i]]=true_nex[nxt[fail[now]][i]];/**/
 64                     Q.push(nxt[now][i]);
 65                 }
 66             }
 67         }
 68     }
 69     ll query(char buf[])
 70     {
 71         int len=strlen(buf);
 72         int now=root;
 73         int res=0;
 74         dp[0]=1;
 75         for(int i=0;i<len;i++)
 76         {
 77             now=nxt[now][buf[i]-'a'];
 78             int temp=now;
 79             while(temp!=root)
 80             {
 81                 dp[i+1]=(dp[i+1]+dp[i+1-ln[temp]]*endd[temp])%mod;
 82                 temp=true_nex[temp];
 83             }
 84         }
 85         return dp[len];
 86     }
 87 }ac;
 88 int n;
 89 char buf[maxn];
 90 int main()
 91 {
 92     int t=1;
 93     for(;t;t--)
 94     {
 95         scanf("%d",&n);
 96         ac.init();
 97         while(n--)
 98         {
 99             scanf("%s",buf);
100             ac.insert(buf);
101         }
102         ac.build();
103         scanf("%s",buf);
104         printf("%lld
",ac.query(buf));
105     }
106     return 0;
107 }

View Code