题目描述

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

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll p=1e9+7;
const int maxn=200050;
ll n;
ll nex[maxn],the_nex[maxn];
ll tree[maxn][30],top,isend[maxn];
ll dp[maxn];
string s,t;
void myinsert(string& s)
{
    ll u=1;
    ll c;
    for(ll i=0; i<s.length(); i++)
    {
        c=s[i]-'a';
        if(!tree[u][c])
        {
            tree[u][c]=++top;
        }
        u=tree[u][c];
    }
    isend[u]=s.length();
}
void getnex()
{
    queue<ll> q;
    for(ll i=0; i<26; i++)
    {
        tree[0][i]=1;
    }
    nex[1]=0;
    q.push(1);
    ll u;
    while(!q.empty())
    {
        u=q.front();
        q.pop();
        for(ll i=0; i<26; i++)
        {
            if(!tree[u][i])
            {
                tree[u][i]=tree[nex[u]][i];
            }
            else
            {
                nex[tree[u][i]]=tree[nex[u]][i];
                q.push(tree[u][i]);
            }
        }
        the_nex[u]=isend[nex[u]]?nex[u]:the_nex[nex[u]];
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    top=1;
    for(ll i=0; i<n; i++)
    {
        cin>>s;
        myinsert(s);
    }
    getnex();
    cin>>t;
    dp[0]=1;
    ll u,k,c;
    u=1;
    for(ll i=1; i<=t.length(); i++)
    {
        dp[i]=0;
        c=t[i-1]-'a';
        k=tree[u][c];
        while(k>1)
        {
            if(isend[k])
            {
                dp[i]+=dp[i-isend[k]];
            }
            k=the_nex[k];
        }
        dp[i]%=p;
        u=tree[u][c];
    }
    cout<<dp[t.length()]<<'\n';
    return 0;
}