后缀的一些运用1

后缀数组的一些运用和小结论1

1.最长重复子串

原题地址

题目大意：给你一个字符串，让你求出至少出现两次的最长子串

解：这是一道板子题，所谓至少出现两次，其实就是我的$hegiht[i]$，即我的$lcp(s_1,s_2)$。所以我只要求出所有的height取最大值即可

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

2.字符加密

原题地址

解：看到环形字符串，下意识就会把它复制一份拼上。之后直接跑一个SA，收集答案时，对于$sa[i]>n$的情况，我们不做处理，因为他不在我要的$[1,n]$的区间内。

3.New Distinct Substrings

原题地址

题目大意：给你一个字符串问有几个本质不同的子串，即若子串形态相同，位置不同，算同一种

解：我们先考虑在sa排序上相邻的两个子串，可以发现$sa[i-1]$可以代表$len(sa[i-1])$种子串，同理$sa[i]$可以代表$len(sa[i])$种子串，他们之间有$len(lcp(sa[i-1],sa[i]))= height[i]$，也就意味着他们有$height[i]$个子串是本质相同的。故$sa[i]和sa[i-1]$对答案的贡献为$len(sa[i-1])+len(sa[i])-height[i]$，对于整个字符串一共有后缀$\frac{n*(n+1)}{2}$个，也就是$\sum_{i=1}^nlen(sa[i])$

所以最后的答案为$\frac{n*(n+1)}{2}-\sum_{i=1}^n height[i]$

4.NSUBSTR - Substrings

原题地址

题目大意：给你一个字符串，问长度为$[1,n]$的子串最多出现了多少次

解：首先我们通过SA可以得到SA中相邻两个字符串的lcp，对于任意两个字符串，有$lcp(s_1,s_2)=\min_{k=i}^j(height[k])$，因此对于长度为L的一个子串，它出现的最多次数，就是在SA上连续$height[i]\ge L$的最长长度，因为他们的lcp是连续的。

如何求出这个长度呢？使用单调栈，先从左往右扫一遍，得到满足$height[i]\ge L$的最左端点位置，再从右往左扫一遍，得到满足$height[i]\ge L$的最右端位置，最后枚举每个位置计算$len[i]=right[i]-left[i]+2$（包括左右端点）

最后算答案的时候，需要利用长度长的出现次数来更新，长度短的出现次数，因为它可能没有被统计到

单调栈代码如下：

struct mono_stack {
	int stk[MAXN], top;
	void push(int x) {
		while (top > 1 && height[stk[top]] >= height[x]) -- top;
		stk[++top] = x;
	}
	int back() {
		return stk[top - 1];
	}
	void clear() {
		top = 0;
	}
};
mono_stack stk;
int ll[MAXN], rr[MAXN];
void solve() {
	stk.push(0);
	for (int i = 1;i <= n;i++)	stk.push(i), ll[i] = stk.back() + 1;
	stk.clear(), stk.push(n + 1);
	for (int i = n;i >= 1;i--) 	stk.push(i), rr[i] = stk.back() - 1;
	for (int i = 1;i <= n;i++) times[height[i]] = max(times[height[i]], rr[i] - ll[i] + 2);
	times[n + 1] = 1;
	for (int i = n;i >= 1;i--) times[i] = max(times[i], times[i + 1]);
}