51nod 1600 Simplr KMP(后缀自动机+维护树上的数据结构）

题意：对于每个位置，统计有多少个相同的字串。

分析：按照题目的意思,把fail树画出来就会发现，对于第i个字符：ans[i] = ans[i-1] + (ans[i-1]-ans[i-1]) + cal(i);

   cal(i)是计算s[1…i-1]所有子串与s[1…i]的最长公共后缀的和。换句话说，根据后缀自动机性质，沿着parent树往上走可以知道对于后缀s[1…i]的所有位置的公共后缀长度以及个数（right集合的大小）。很容易可以计算出cal(i), 只要每次新增一个字符的时候，在parent树上往根走，边走边统计 val[i]*(right[pre[i]]-right[i])。由于博主我是在建后缀自动机的同时计算ans，所以parent树是动态地边的，所以博主用了LCT去维护。

吐槽：看问题的角度果然可以有好多，显然下面代码能折射出我看问题的角度显然不太好。为了这道题，苦苦地学了LCT，然而后来看别人博客发现可以直接用树链剖分写的。

/************************************************ Author :DarkTong Created Time :2016/9/6 22:58:31 File Name :51nod_simpleKMP.cpp *************************************************/#include <bits/stdc++.h> using namespace std; typedef unsigned long long ULL; typedef long long LL; const int INF = 0x3f3f3f3f; const double eps = 1e-9; const int MOD = 1e9+7; const int maxn = 2*100000 + 100; LL ans[maxn]; struct Splay_Tree {int ch[maxn][2], pre[maxn], dpre[maxn];// dpre用于树-树连接// pre用于树内连接int lazy[maxn], mval[maxn], mr[maxn];LL sum[maxn];int go[maxn][26], right[maxn], val[maxn];int sz, last, root;void pushdown(int x){int l = ch[x][0], r = ch[x][1];if(l)lazy[l] += lazy[x], right[l] += lazy[x], mr[l] += lazy[x];if(r)lazy[r] += lazy[x], right[r] += lazy[x], mr[r] += lazy[x];lazy[x] = 0;mr[x] = max(right[x], max(mr[l], mr[r]));}void pushup(int x){sum[x] = (sum[ch[x][0]] + sum[ch[x][1]] + val[x]*mval[x])%MOD;mr[x] = max(right[x], max(mr[ch[x][0]], mr[ch[x][1]]));//ch[x][1] 不是 x的儿子，因为x不是根。 }//旋转操作(ok)，请注意：对于被旋转的元素，其dpre=0，也就是说是对辅助树在操作，不影响到原树。void rotate(int x){int y = pre[x], d = (ch[y][1]==x);ch[y][d] = ch[x][!d]; pre[ch[x][!d]] = y; pre[x] = pre[y]; pre[y] = x;ch[x][!d] = y;if(dpre[y]) dpre[y]=0, dpre[x]=1;else ch[pre[x]][ch[pre[x]][1]==y] = x;pushup(y);// pushup(x); }//直接访问节点o,并将其选转至根部void P(int x){if(!dpre[x]) P(pre[x]); //找重链的根，然后把标志向下传一遍 pushdown(x);}void splay(int x){P(x);while(!dpre[x]){int f = pre[x], ff = pre[f];if(dpre[f]) rotate(x);else if( (ch[ff][1]==f) == (ch[f][1]==x) ) rotate(f), rotate(x);else rotate(x), rotate(x);}pushup(x);}//AuxiliaryTree链接操作(数据更新)void Access(int x){int y = 0;for(;x;y=x, x=pre[x]){splay(x); //为了去掉元重儿子，旋转后儿子在其左子树dpre[ch[x][1]] = 1; //去掉元重儿子ch[x][1] = y;dpre[y] = 0; //加入新的重儿子vmval[x] = right[x] - mr[ch[x][1]];pushup(x);}}//加边，连接两棵树，u->v;void link(int u, int v){Access(u);pre[u]=v;dpre[u] = 1;Access(u);}void cut(int x){Access(x); splay(x);int l = ch[x][0];pre[l] = 0; dpre[l] = 1;ch[x][0] = 0;Access(x);}int fa(int u){Access(u);splay(u);u = ch[u][0];while(ch[u][1]) u = ch[u][1];return u;}void SAM(){last = root = sz = 1;}void ini(int sz, int v){val[sz] = v;mval[sz] = 0;ch[sz][0]=ch[sz][1]=0;dpre[sz] = 1;pre[sz]=sum[sz]=lazy[sz]=right[sz]=0;mr[sz]=0;memset(go[sz], 0, sizeof go[sz]);}void extend(int w, int th){int p = last;int np = ++sz; ini(sz, val[p]+1); //叶子节点while(p && go[p][w] == 0) go[p][w] = np, p = fa(p);if(p == 0) link(np, root);else{int q = go[p][w];if(val[p] + 1 == val[q]) link(np, q);else{int nq = ++sz; ini(sz, val[p]+1); //非叶子节点memcpy(go[nq], go[q], sizeof go[q]);mr[nq] = right[nq] = right[q]; mval[nq] = right[q]; int faq = fa(q);cut(q); link(q, nq); link(np, nq); link(nq, faq); while(p && go[p][w] == q) go[p][w] = nq, p = fa(p);}}last = np;ans[th] = cal(np);}LL cal(int x){x = fa(x);Access(x);splay(x);//updatelazy[x]++;right[x]++;mval[x] = right[x];pushup(x);return sum[x];} }slt; char s[maxn];int main() { // freopen("out.txt", "r", stdin); // freopen("xx1.txt", "w", stdout);int T, cas=1, n;scanf("%d%s", &n, s);slt.SAM();slt.ini(1, 0);for(int i=0;i<n;++i){slt.extend(s[i]-'a', i);} // for(int i=0;i<n;++i) cout<<ans[i]<<" "; cout<<endl;for(int i=2;i<n;++i) ans[i] = (2*ans[i-1]-ans[i-2]+ans[i]+MOD)%MOD;for(int i=0;i<n;++i) printf("%lld\n", ans[i]);return 0; }

转载于:https://www.cnblogs.com/DarkTong/p/5851772.html

总结

以上是生活随笔为你收集整理的51nod 1600 Simplr KMP(后缀自动机+维护树上的数据结构）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。