[洛谷 3181][HAOI2016] 找相同字符【后缀数组+单调栈】

• 2018-02-24
• 0
• 0

Problem:

题目描述

给定两个字符串，求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。两个方案不同当且仅当这两个子串中有一个位置不同。

输入输出格式

输入格式：

两行，两个字符串s1，s2，长度分别为n1，n2。1 <=n1, n2<= 200000，字符串中只有小写字母

输出格式：

输出一个整数表示答案

输入输出样例

aabb
bbaa

10

Solution:

题目要求在两个串 s1, s2 的公共子串数，可以等价于后缀的前缀相同的方案数。

那么我们可以令 s = s1 + s2，即将两个串连接，然后用后缀数组进行后缀排序。

但是我们发现，这样会导致 s2 对 s1 的后缀造成影响。

考虑在 s1 和 s2 之间补一个值最大的字符，将 s1 和 s2 隔开即可。

求出后缀字典序后，我们要怎么快速统计后缀的前缀相同的方案数呢？

考虑到较长的公共前缀包含了更短的公共前缀，所以我们可以用单调栈维护当前的前缀，以快速计算方案数。

Code: O(nlogn), 其中n=|s1|+|s2| [11476K, 840MS]

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 400005;

char s[MAXN];
int n1, n, SA[MAXN], rnk[MAXN], ht[MAXN], sum[MAXN];
int stk[MAXN], tops = 0;
ll sch[MAXN], ans = 0;

inline void buildSA(int m){
	int *x = new int[MAXN], *y = new int[MAXN], *cnt = new int[MAXN];
	for(register int i = 0; i < m; i++) cnt[i] = 0;
	for(register int i = 0; i < n; i++) cnt[x[i] = s[i]]++;
	for(register int i = 1; i < m; i++) cnt[i] += cnt[i - 1];
	for(register int i = n - 1; i >= 0; i--) SA[--cnt[x[i]]] = i;
	for(register int k = 1; k <= n; k <<= 1){
		int p = 0;
		for(register int i = n - k; i < n; i++) y[p++] = i;
		for(register int i = 0; i < n; i++) if(SA[i] >= k) y[p++] = SA[i] - k;
		for(register int i = 0; i < m; i++) cnt[i] = 0;
		for(register int i = 0; i < n; i++) cnt[x[y[i]]]++;
		for(register int i = 1; i < m; i++) cnt[i] += cnt[i - 1];
		for(register int i = n - 1; i >= 0; i--) SA[--cnt[x[y[i]]]] = y[i];
		swap(x, y), p = 1, x[SA[0]] = 0;
		for(register int i = 1; i < n; i++) x[SA[i]] = (y[SA[i]] == y[SA[i - 1]] && y[SA[i] + k] == y[SA[i - 1] + k]) ? p - 1 : p++;
		if(p == n) break;
		m = p;
	}
	for(register int i = 0; i < n; i++) rnk[SA[i]] = i;
	int k = 0, j;
	for(register int i = 0; i < n; ht[rnk[i++]] = k)
		for(k ? k-- : 0, j = SA[rnk[i] - 1]; s[i + k] == s[j + k]; k++);
	delete []x, delete []y, delete []cnt;
}

int main(){
	scanf("%s", s), n1 = strlen(s), s[n1++] = 123;  // Put a sentinel 'z' + 1 to guarantee prefixes of two strings totally apart
	scanf("%s", s + n1), n = strlen(s + n1) + n1, s[n++] = 96;  // Put a sentinel 'a' - 1
	for(register int i = 0; i < n; i++) s[i] -= 96;
	buildSA(28);
	for(register int i = 1; i < n - 1; i++) sum[i] = sum[i - 1] + (SA[i] < n1);
	for(register int i = 1; i < n - 1; i++){
		while(tops && ht[stk[tops]] > ht[i]) tops--;
		stk[++tops] = i, sch[tops] = sch[tops - 1] + (ll)(sum[i - 1] - sum[stk[tops - 1] - 1]) * ht[i];
		if(SA[i] >= n1) ans += sch[tops];
	}
	tops = 0;
	for(register int i = 1; i < n - 1; i++) sum[i] = sum[i - 1] + (SA[i] >= n1);
	for(register int i = 1; i < n - 1; i++){
		while(tops && ht[stk[tops]] > ht[i]) tops--;
		stk[++tops] = i, sch[tops] = sch[tops - 1] + (ll)(sum[i - 1] - sum[stk[tops - 1] - 1]) * ht[i];
		if(SA[i] < n1) ans += sch[tops];
	}
	printf("%lld\n", ans);
	return 0;
}