題目鏈接：戳我

求不同的子串個數（相同但出現在不同位置的算一個）——就是一個SAM裸題啦！

我們直接一個一個添加節點的時候統計答案即可（每次多出來的都是last里面存的）

但是數太大了，記得要map或者離散化哦qwq

#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<map> #define MAXN 200010 using namespace std; int n,m,tot=1,last=1,cnt; long long ans; // map<int,int>ex; struct Node {int ff,len;map<int,int>ch; }t[MAXN<<1]; inline void extend(int c) {int p=last,np=++tot;last=np;t[np].len=t[p].len+1;while(p&&!t[p].ch.count(c)) t[p].ch[c]=np,p=t[p].ff;if(!p) t[np].ff=1;else{int q=t[p].ch[c];if(t[q].len==t[p].len+1) t[np].ff=q;else{int nq=++tot;t[nq]=t[q];t[nq].len=t[p].len+1;t[np].ff=t[q].ff=nq;while(p&&t[p].ch[c]==q) t[p].ch[c]=nq,p=t[p].ff;}} } int main() {#ifndef ONLINE_JUDGEfreopen("ce.in","r",stdin);#endifscanf("%d",&n);for(int i=1;i<=n;i++){int cur;scanf("%d",&cur);// if(!ex.count(cur)) ex[cur]=++cnt;extend(cur);ans+=t[last].len-t[t[last].ff].len;printf("%lld\n",ans);}return 0; }

轉載于:https://www.cnblogs.com/fengxunling/p/10763632.html

總結

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

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