题目链接

题面：

给定n个串，从每个串中选一个子串（可以为空），这些子串按顺序组成一个新串。
问本质不同的新串的个数。

我们倒着来考虑这些串。
我们设 dp [ i ] [ j ] 为倒序考虑到 第 i 个串 且 新串以 j 开头的本质不同的数量。
我们设 f [ i ] [ j ] 为考虑到 第 i 个串 且 倒序考虑到后缀自动机上第 j 个节点的本质不同的数量。
考虑转移：

if(nt[now][j]) f[now]=(f[now]+f[nt[now][j]])%mod;
else f[now]=(f[now]+dp[j])%mod;

如果当前考虑到了后缀自动机上第now个节点。
后缀自动机上从根节点出来到某一节点一定是某字符串的一个子串且这些子串本质不同。
后缀自动机上从根节点出来到某一终止节点一定是某字符串的一个后缀。
若某些后缀的前缀相同，那么他们的前缀共用一条路径。
即后缀自动机上，任意子串都是本质不同的。

我们逆拓扑序考虑。
假设当前节点nt [ now ] [ j ] 存在，即当前字符后面连接有字符 j ，为了不重复计算，我们令f [ now ] = ( f [ now ] + f [ nt [ now ] [ j ] ] ) % mod。因为在当前串上接上字符 j ，那么此后串上的字符 j 开头的子串都算进去了。
若 nt [ now ] [ j ] 不存在 ，即当前字符后面没有连接字符 j，那么f [ now ] = ( f [ now ] + dp [ j ] ) % mod。此时当前字符后面可以连接此后串上 j 开头的子串。

void _count(void)
    {

        for(int i=1;i<=cnt;i++) x[len[i]]++;
        for(int i=1;i<=cnt;i++) x[i]+=x[i-1];
        for(int i=1;i<=cnt;i++) y[x[len[i]]--]=i;
        for(int i=cnt;i>=1;i--)
        {
            int now=y[i];
            f[now]=1;
            for(int j=0;j<26;j++)
            {
                if(nt[now][j]) f[now]=(f[now]+f[nt[now][j]])%mod;
                else f[now]=(f[now]+dp[j])%mod;
            }
        }
        for(int i=0;i<26;i++)
            if(nt[1][i]) dp[i]=f[nt[1][i]];

        return ;

    }

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#define ll long long
#define llu unsigned ll
using namespace std;
const int maxn=1000100;
const int mod=1e9+7;
char str[maxn];
ll dp[26];
ll f[maxn];
string s[2010];

struct Sam
{
    int last,cnt;
    int nt[maxn<<1][26],fa[maxn<<1];
    int len[maxn<<1],sum[maxn<<1];
    int x[maxn<<1],y[maxn<<1];
    void init(int n)
    {
        last=1;
        cnt=1;
        fa[1]=0;
        len[1]=0;

        for(int i=0;i<=n;i++)
        {
            fa[i]=0;
            len[i]=0;
            sum[i]=0;
            x[i]=0;
            memset(nt[i],0,sizeof(nt[i]));
        }
    }

    void _insert(int c)
    {
        int nowp=++cnt,p=last;
        len[nowp]=len[last]+1;

        while(p&&!nt[p][c]) nt[p][c]=nowp,p=fa[p];
        if(!p) fa[nowp]=1;
        else
        {
            int q=nt[p][c];
            if(len[q]==len[p]+1) fa[nowp]=q;
            else
            {
                int nowq=++cnt;
                len[nowq]=len[p]+1;
                memcpy(nt[nowq],nt[q],sizeof(nt[q]));

                fa[nowq]=fa[q];
                fa[nowp]=fa[q]=nowq;

                while(p&&nt[p][c]==q) nt[p][c]=nowq,p=fa[p];
            }
        }
        last=nowp;
        sum[last]=1;
        return ;
    }

    void _count(void)
    {

        for(int i=1;i<=cnt;i++) x[len[i]]++;
        for(int i=1;i<=cnt;i++) x[i]+=x[i-1];
        for(int i=1;i<=cnt;i++) y[x[len[i]]--]=i;
        for(int i=cnt;i>=1;i--)
        {
            int now=y[i];
            f[now]=1;
            for(int j=0;j<26;j++)
            {
                if(nt[now][j]) f[now]=(f[now]+f[nt[now][j]])%mod;
                else f[now]=(f[now]+dp[j])%mod;
            }
        }
        for(int i=0;i<26;i++)
            if(nt[1][i]) dp[i]=f[nt[1][i]];

        return ;

    }

    void creat(int q)
    {
        int len=s[q].size();

        init(len*2+10);
        for(int i=0;i<len;i++)
            _insert(s[q][i]-'a');
        _count();

        return ;
    }
}sam;


int main(void)
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%s",str);
        s[i]=str;
    }
    for(int i=n;i>=1;i--)
        sam.creat(i);
    ll ans=0;
    for(int i=0;i<26;i++)
        ans=(ans+dp[i])%mod;
    printf("%lld\n",ans+1);


    return 0;
}