[HAOI2016]找相同字符(后缀数组+单调栈)

[HAOI2016]找相同字符(后缀数组+单调栈)

题面

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

分析

我们把两个字符串接在一起，中间加一个分隔符。如( ext{AABB})和( ext{BBAA})变成( ext{AABB|BBAA})。我们考虑两个相同字串,如( ext{BB}),它在新串中对应了两个后缀(BB|BBAA)和( ext{BBAA})的LCP. 容易发现,LCP永远不会同时包括分隔符两端的字符，这样就保证了两个子串是从原来两个字符串中的某个取出的。

所以我们可以枚举两个后缀,然后用ST表查询最小值求出LCP.但是这样的复杂度是(O(n^2))的，需要优化。

考虑到利用Height数组求任意两个后缀的LCP时的独特性质：两个后缀的LCP为对应区间height的最小值。也就是说排序后，一个后缀越往后数LCP的长度越小。这样，我们就可以用单调栈维护这个最小值。分A串的子串在前、B的子串在前两种情况分别用单调栈求出答案

代码

(法1)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define maxn 400000
using namespace std;
typedef long long ll;
int n,m,tot;
char a[maxn+5],b[maxn+5],s[maxn+5];
 
void sort(int *ans,int *fi,int *se,int sz,int maxv){
	static int buck[maxn+5];
	for(int i=0;i<=maxv;i++) buck[i]=0;
	for(int i=1;i<=sz;i++) buck[fi[i]]++;
	for(int i=0;i<=maxv;i++) buck[i]+=buck[i-1];
	for(int i=sz;i>=1;i--) ans[buck[fi[se[i]]]--]=se[i]; 
} 
int sa[maxn+5];
int rk[maxn+5];
int height[maxn+5];
void suffix_sort(char *str,int n,int m){
	static int se[maxn+5];
	for(int i=1;i<=n;i++){
		rk[i]=str[i];
		se[i]=i;
	}
	sort(sa,rk,se,n,m);
	for(int k=1;k<=n;k*=2){
		int p=0;
		for(int i=n-k+1;i<=n;i++) se[++p]=i;
		for(int i=1;i<=n;i++){
			if(sa[i]>k) se[++p]=sa[i]-k;
		}
		sort(sa,rk,se,n,m);
		swap(se,rk);
		p=1; 
		rk[sa[1]]=1;
		for(int i=2;i<=n;i++){
			if(se[sa[i-1]]==se[sa[i]]&&se[sa[i-1]+k]==se[sa[i]+k]) rk[sa[i]]=p; 
			else rk[sa[i]]=++p; 
		}
		if(p==n) break;
		m=p;
	}	
} 
void get_height(char *str,int n,int m){
	suffix_sort(str,n,m);
	for(int i=1;i<=n;i++) rk[sa[i]]=i;
	int k=0;
	for(int i=1;i<=n;i++){
		if(k) k--;
		int j=sa[rk[i]-1];
		while(str[i+k]==str[j+k]) k++;
		height[rk[i]]=k;
	}
}

struct node{
	ll a;
	ll b;
	int h;
	node(){
		
	}
	node(ll _a,ll _b,int _h){
		a=_a;
		b=_b;
		h=_h;
	}
	friend bool operator < (node p,node q){
		return p.h<q.h;
	}
	friend node operator + (node p,node q){
		return node(p.a+q.a,p.b+q.b,p.h);
	}
};
int top=0;
node stk[maxn+5];

int main(){
	scanf("%s",a+1);
	scanf("%s",b+1);
	n=strlen(a+1),m=strlen(b+1);
	tot=0;
	for(int i=1;i<=n;i++) s[++tot]=a[i];
	s[++tot]='|';
	for(int i=1;i<=n;i++) s[++tot]=b[i];
	get_height(s,tot,128);
	ll ans=0;
	ll cnta=0,cntb=0;
	for(int i=2;i<=tot;i++){
		node now=node(0,0,height[i]);
		if(sa[i-1]<=n) now.a++;
		else if(sa[i-1]>n+1) now.b++; 
		while(top>0&&now<stk[top]){
			cnta-=stk[top].a*stk[top].h;
			cntb-=stk[top].b*stk[top].h;
			now=now+stk[top];
			top--;
		}
		stk[++top]=now;
		cnta+=now.a*now.h;
		cntb+=now.b*now.h;
		if(sa[i]<=n) ans+=cntb;
		else if(sa[i]>n+1) ans+=cnta;
	}
	printf("%lld
",ans);
}