傳送門

心態崩了++

后綴自動機板子題[考場上要是不會后綴自動機就崩了T^T]

可以看出 每次答案的貢獻就是和原來本質不同的子串數量

根據SPOJ7258我們可以得到 本質不同的子串數量可以通過建出自動機 樹形dp解決

我們需要知道的就是 連向它的那個鏈

就是我們建立自動機的時候的那個找的p

直接求一下就好了

另外的理解方式就是我們要求本質不同的前綴數量 那么就是parent樹上len的定義 直接len[x]-len[fa]就是答案

時間復雜度O(n)

寫完了調過樣例交了一發WA 然后看到STD里開longlong了改了一發longlong又一發WA 然后心態崩掉 一點一點重推 最后發現 我輸出沒改 還是%d [手動再見]

附代碼。

#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<map> #define inf 20021225 #define ll long long #define mxn 100010 using namespace std; struct node{int fa,len;map<int,int> ch;}t[mxn*4]; int poi,lt,rt,n;ll ans; void insert(int c) {int p=lt,np=lt=++poi; t[np].len=t[p].len+1;for(;p&&!t[p].ch[c];p=t[p].fa) t[p].ch[c]=np;ans+=t[np].len;if(!p){t[np].fa=rt;return;}int q=t[p].ch[c];if(t[q].len==t[p].len+1){ans-=t[q].len;t[np].fa=q;return;}int nq=++poi; t[nq].len=t[p].len+1;t[nq].ch=t[q].ch; ans-=t[nq].len;t[nq].fa=t[q].fa; t[q].fa=t[np].fa=nq;for(;p&&t[p].ch[c]==q;p=t[p].fa) t[p].ch[c]=nq; } int main() {int x;scanf("%d",&n);lt=rt=++poi;for(int i=1;i<=n;i++){scanf("%d",&x);insert(x);printf("%lld\n",ans);}return 0; }

本題還有一個非常優秀的做法就是SA

我們發現 要求本質不同的前綴數量 那么就是 len - max_lcp 我們發現 這個不就是SA的height嗎！

我們可以通過倒過來刪除的操作 鏈表維護一通 也是可以AC的~

時間復雜度是O(nlgn) 瓶頸在于求SA 如果你是大佬寫DC3的話請無視

我這輩子也不可能寫DC3的[Flag]

轉載于:https://www.cnblogs.com/hanyuweining/p/10321915.html

總結

以上是生活随笔為你收集整理的BZOJ 4516 [Sdoi2016] 生成魔咒的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。