BZOJ4516: [Sdoi2016]生成魔咒(后缀自动机)-白红宇

BZOJ4516: [Sdoi2016]生成魔咒(后缀自动机)

阅读量：4690 次

发布时间：2019-06-09

本文共 1908 字，大约阅读时间需要 6 分钟。

Description

魔咒串由许多魔咒字符组成，魔咒字符可以用数字表示。例如可以将魔咒字符 1、2 拼凑起来形成一个魔咒串 [1,2]。

一个魔咒串 S 的非空字串被称为魔咒串 S 的生成魔咒。

例如 S=[1,2,1] 时，它的生成魔咒有 [1]、[2]、[1,2]、[2,1]、[1,2,1] 五种。S=[1,1,1] 时，它的生成魔咒有 [1]、

[1,1]、[1,1,1] 三种。最初 S 为空串。共进行 n 次操作，每次操作是在 S 的结尾加入一个魔咒字符。每次操作后都

需要求出，当前的魔咒串 S 共有多少种生成魔咒。

Input

第一行一个整数 n。

第二行 n 个数，第 i 个数表示第 i 次操作加入的魔咒字符。

1≤n≤100000。,用来表示魔咒字符的数字 x 满足 1≤x≤10^9

Output

输出 n 行，每行一个数。第 i 行的数表示第 i 次操作后 S 的生成魔咒数量

Sample Input

1 2 3 3 3 1 2

Sample Output

解题思路：

实际上是找不同的子串个数。

一个一个插，那么我们可以在增量构造时增量统计。

新产生的字符串长度为其节点合并时的长度差。

体现在自动机上就是与pre节点的长度差。

代码：

1 #include 2 #include
      
        3 #include
       
         4 #include
        
          5 struct sant{ 6     std::map
         
          tranc; 7     int len; 8     int pre; 9 }s[1000000];10 int siz;11 int fin;12 int n;13 int Insert(int c)14 {15     int nwp,lsp,nwq,lsq;16     nwp=++siz;17     s[nwp].len=s[fin].len+1;18     for(lsp=fin;lsp&&(s[lsp].tranc.find(c)==s[lsp].tranc.end());lsp=s[lsp].pre)19         s[lsp].tranc[c]=nwp;20     if(!lsp)21         s[nwp].pre=1;22     else{23         lsq=s[lsp].tranc[c];24         if(s[lsq].len==s[lsp].len+1)25             s[nwp].pre=lsq;26         else{27             nwq=++siz;28             s[nwq]=s[lsq];29             s[nwq].len=s[lsp].len+1;30             s[nwp].pre=s[lsq].pre=nwq;31             while((s[lsp].tranc.find(c)!=s[lsp].tranc.end())&&s[lsp].tranc[c]==lsq)32             {33                 s[lsp].tranc[c]=nwq;34                 lsp=s[lsp].pre;35             }36         }37     }38     fin=nwp;39     return s[nwp].len-s[s[nwp].pre].len;40 }41 int main()42 {43     fin=++siz;44     scanf("%d",&n);45     long long ans=0;46     for(int i=1;i<=n;i++)47     {48         int tmp;49         scanf("%d",&tmp);50         ans+=(long long)Insert(tmp);51         printf("%lld\n",ans);52     }53     return 0;54 }