字符串杂题

Little Elephant and Strings

来源：CF204E

做法一：$\mathrm{SA}+$ 主席树   

可以把所有串拼在一起，然后中间用特殊分隔符分开.   

考虑处理第 $\mathrm{i}$ 个串的 $\mathrm{l}$ 位置开始的子串. 

显然这个 $\mathrm{r}$ 具有单调性，所以可以二分最大的 $\mathrm{r}$. 

这个东西用双指针扫，然后每个区间用主席树查一下编号种类即可.   

时间复杂度为 $\mathrm{O(n \log n)}$.   

做法二： $\mathrm{SAM}$

构建广义后缀自动机，然后插入串的时候暴力更新 $\mathrm{pre}$ 的信息. 

最后查询的时候把串放到自动机上跑一遍倍增求一下即可. 

时间复杂度也是 $O(n \log n)$.    

p.s. 暴力跳的方法可能不太优美. 

这个问题等价于给定树上若干个点，求这些点所构成的树链的并.  

可以将所有点离线，按照 $\mathrm{dfs}$ 序排序，然后在相邻 $\mathrm{lca}$ 处减掉

做法三：$\mathrm{SA}+$单调队列.  

若固定左端点 $\mathrm{l}$, 则显然要找到最大的 $\mathrm{r}$ 使得种类不小于 $K$.  

所以可以用双指针维护数量恰好为 $\mathrm{K}$ 的区间，并维护这个区间的 $\mathrm{lcp}$.

对于一个位置 $\mathrm{p}$ 来说， $\mathrm{p}$ 的贡献就是包含 $\mathrm{p}$ 的 $\mathrm{lcp}$ 最大的.  

这个东西用线段树或单调队列维护一下即可.  

做法二：

#include 
#include 
#include 
#include 
#define N  200009 
#define ll long long 
#define pb push_back 
#define setIO(s) freopen(s".in","r",stdin) 
using namespace std; 
char str[N], tp[N]; 
int n, K, st[N], ed[N], pre[N << 1], len[N << 1], ch[N << 1][26]; 
int last, tot, vis[N], cn[N], fa[N][19]; 
void extend(int c) {
	if(ch[last][c]) {
		int p = last, q = ch[last][c]; 
		if(len[q] == len[p] + 1) last = q; 
		else {
			int nq = ++ tot; 
			len[nq] = len[p] + 1; 
			vis[nq] = vis[q], cn[nq] = cn[q]; 
			memcpy(ch[nq], ch[q], sizeof(ch[q])); 
			pre[nq] = pre[q], pre[q] = nq; 
			for(; p && ch[p][c] == q; p = pre[p]) 
				ch[p][c] = nq; 
			last = nq; 
		}
	}
	else {
		int p = last, np = ++ tot; 
		len[np] = len[p] + 1, last = np; 
		for(; p && !ch[p][c]; p = pre[p]) 
			ch[p][c] = np; 
		if(!p) pre[np] = 1; 
		else {
			int q = ch[p][c]; 
			if(len[q] == len[p] + 1) pre[np] = q; 
			else {
				int nq = ++ tot; 
				len[nq] = len[p] + 1; 
				vis[nq] = vis[q], cn[nq] = cn[q]; 
				memcpy(ch[nq], ch[q], sizeof(ch[q])); 
				pre[nq] = pre[q], pre[np] = pre[q] = nq; 
				for(; p && ch[p][c] == q; p = pre[p]) 
					ch[p][c] = nq; 
			}
		}
	}
}
int jump(int x) {
	for(int i = 18; i >= 0; -- i) {
		if(cn[fa[x][i]] < K) x = fa[x][i]; 
	}
	return x;  
}
int main() {
	// setIO("input"); 
	scanf("%d%d", &n, &K); 
	last = tot = 1; 
	for(int i = 1; i <= n ; ++ i) {
		scanf("%s", tp + 1); 
		st[i] = ed[i - 1] + 1; 
		ed[i] = st[i] + strlen(tp + 1) - 1;
		last = 1;  
		for(int j = st[i]; j <= ed[i]; ++ j) {
			str[j] = tp[j - st[i] + 1]; 
			extend(str[j] - 'a');   
			int p = last; 
			while(p && vis[p] != i) {
				vis[p] = i, ++ cn[p], p = pre[p];  
			}
		}
	}   
	for(int i = 1; i <= tot; ++ i) fa[i][0] = pre[i]; 
	for(int i = 1; i < 19  ; ++ i) 
		for(int j = 1; j <= tot; ++ j) fa[j][i] = fa[fa[j][i - 1]][i - 1];    
	cn[0] = N; 
	for(int i = 1; i <= n ; ++ i) {
		int p = 1; 
		ll ans = 0ll; 
		for(int j = st[i]; j <= ed[i] ; ++ j) {
			int c = str[j] - 'a';  
			p = ch[p][c];  
			int nex = jump(p); 
			if(cn[nex] >= K) ans += len[nex];   
			else {
				nex = pre[nex]; 
				if(nex && cn[nex] >= K) ans += len[nex];  
			} 
		}
		printf("%I64d", ans); 
		if(i != n) printf(" "); 
	}
	return 0; 
}

Paper task

来源：CF653F

这道题的重点是模拟，后缀自动机只是帮助统计本质不同的工具.  

p.s. 后缀数组的做法类似，是利用 $\mathrm{height[x]}$ 数组来保持本质不同的条件.   

$\mathrm{parent}$ 树和 $\mathrm{height}$ 数组都是有助于思考的同类型工具. 

#include 
#include 
#include