题目描述
你有一个字符串S，一开始为空串，要求支持两种操作
在S后面加入字母C
删除S最后一个字母
问每次操作后S有多少个两两不同的连续子串
输入
一行一个字符串Q,表示对S的操作
如果第i个字母是小写字母c,表示第一种加字母c的操作
如果为-表示删除操作，保证所有删除操作前S都非空
|Q|<=10^5
输出
输出|Q|行，第i行表示i个操作之后S内有多少个不同子串
样例输入
aba-caba
样例输出
135 3 6 91217
题解
广义后缀自动机+树链的并+STL-set
题目给出的字符串是一棵Trie的形式，我们对其建出广义后缀自动机。
那么每次我们要求的就是：Trie树上当前所有点在后缀自动机pre树到根节点的路径所覆盖的所有点的 $dis[pre[i]]-dis[i]$ 之和，即树链的并的长度。
我们使用STL-set维护动态插入删除节点的树链的并即可。
时间复杂度 $O(26n+n\log n)$ 。
第一次写正常的广义SAM = =
#include#include #include #include #define N 200010using namespace std;set s;set ::iterator it;char str[N];int tc[N][26] , tf[N] , tt = 1 , pos[N] , c[N][26] , pre[N] , dis[N] , tot = 1 , head[N] , to[N] , next[N] , cnt , fa[N][20] , deep[N] , log[N] , vp[N] , rp[N] , tp;inline int insert(int x , int p){ if(c[p][x]) { int q = c[p][x]; if(dis[q] == dis[p] + 1) return q; else { int nq = ++tot; memcpy(c[nq] , c[q] , sizeof(c[q])); dis[nq] = dis[p] + 1 , pre[nq] = pre[q] , pre[q] = nq; while(p && c[p][x] == q) c[p][x] = nq , p = pre[p]; return nq; } } else { int np = ++tot; dis[np] = dis[p] + 1; while(p && !c[p][x]) c[p][x] = np , p = pre[p]; if(!p) pre[np] = 1; else { int q = c[p][x]; if(dis[q] == dis[p] + 1) pre[np] = q; else { int nq = ++tot; memcpy(c[nq] , c[q] , sizeof(c[q])); dis[nq] = dis[p] + 1 , pre[nq] = pre[q] , pre[np] = pre[q] = nq; while(p && c[p][x] == q) c[p][x] = nq , p = pre[p]; } } return np; }}void build(int x){ int i; for(i = 0 ; i < 26 ; i ++ ) if(tc[x][i]) pos[tc[x][i]] = insert(i , pos[x]) , build(tc[x][i]);}inline void add(int x , int y){ to[++cnt] = y , next[cnt] = head[x] , head[x] = cnt;}void dfs(int x){ int i; vp[x] = ++tp , rp[tp] = x; for(i = 1 ; i <= log[deep[x]] ; i ++ ) fa[x][i] = fa[fa[x][i - 1]][i - 1]; for(i = head[x] ; i ; i = next[i]) fa[to[i]][0] = x , deep[to[i]] = deep[x] + 1 , dfs(to[i]);}inline int lca(int x , int y){ int i; if(deep[x] < deep[y]) swap(x , y); for(i = log[deep[x] - deep[y]] ; ~i ; i -- ) if(deep[x] - deep[y] >= (1 << i)) x = fa[x][i]; if(x == y) return x; for(i = log[deep[x]] ; ~i ; i -- ) if(deep[x] >= (1 << i) && fa[x][i] != fa[y][i]) x = fa[x][i] , y = fa[y][i]; return fa[x][0];}int main(){ int q , i , now = 1 , x , y; long long ans = 0; scanf("%s" , str) , q = strlen(str); for(i = 0 ; i < q ; i ++ ) { if(str[i] == '-') now = tf[now]; else { if(!tc[now][str[i] - 'a']) tc[now][str[i] - 'a'] = ++tt , tf[tt] = now; now = tc[now][str[i] - 'a']; } } pos[1] = 1 , build(1); for(i = 2 ; i <= tot ; i ++ ) add(pre[i] , i) , log[i] = log[i >> 1] + 1; dfs(1); now = 1; for(i = 0 ; i < q ; i ++ ) { if(str[i] == '-') { ans -= dis[pos[now]] , s.erase(vp[pos[now]]); x = y = 0 , it = s.upper_bound(vp[pos[now]]); if(it != s.end()) x = rp[*it]; if(it != s.begin()) y = rp[*--it]; if(x) ans += dis[lca(pos[now] , x)]; if(y) ans += dis[lca(pos[now] , y)]; if(x && y) ans -= dis[lca(x , y)]; now = tf[now]; } else { now = tc[now][str[i] - 'a'] , ans += dis[pos[now]]; x = y = 0 , it = s.upper_bound(vp[pos[now]]); if(it != s.end()) x = rp[*it]; if(it != s.begin()) y = rp[*--it]; if(x) ans -= dis[lca(pos[now] , x)]; if(y) ans -= dis[lca(pos[now] , y)]; if(x && y) ans += dis[lca(x , y)]; s.insert(vp[pos[now]]); } printf("%lld\n" , ans); } return 0;}