洛谷题目链接:[HAOI2016]找相同字符
题目描述
给定两个字符串，求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。两个方案不同当且仅当这两个子串中有一个位置不同。
输入输出格式
输入格式：
两行，两个字符串s1，s2，长度分别为n1，n2。1 <=n1, n2<= 200000，字符串中只有小写字母
输出格式：
输出一个整数表示答案
输入输出样例
输入样例#1：
aabb
bbaa
输出样例#1：
10
题意: 将(s2)接在(s1)的后面,问$$sum _{iin[1,n1],jin[n1+1,n1+n2]}lcp(suffix(i),suffix(j))$$
题解: 首先考虑如何求出任意两后缀的(LCP)(例题[AHOI2013]差异),首先我们知道(LCP(i, j) = min{lcp(k-1, k)},kin [i+1, j]).也就是我们可以通过ST表预处理(height)数组的最小值,然后对于两个后缀(O(1))查询.然而这里枚举两个后缀的时间复杂度是(O(n^2))的,也就是说这样求是不行的.
我们再观察一下这个式子:(LCP(i, j) = min{lcp(k-1, k)},kin [i+1, j]),可以发现,如果我们求出(i)左边第一个小于(height[i])的位置(L[i]),右边第一个小于等于(height[i])的位置(R[i]),那么左边的([L[i],i])这个区间内的点作为起点的后缀都可以和右边([i,R[i]])内的点为起点的后缀进行组合,且他们的(LCP)的长度都是(height[i]),那么这样我们就得到了一个单调栈求任意两后缀的(O(n))做法.
那么如果将(s2)接在(s1)的后面,求一下任意两后缀的(LCP)之和,那么总答案就被统计出来了.
然而这样统计的话会有个问题:(s1)内的后缀互相匹配,(s2)内的后缀也互相匹配,导致答案增加,所以我们要减掉这一部分的答案.
然而这样统计依然有问题.我们考虑这样两个串:(s1="aaaa",s2="aaaa),那么在(s2)接在(s1)后面之后,在(s1)内的后缀互相匹配时会加上一部分(s2)的长度.为了保证(s1)内互相匹配时不会受到(s2)的印象,我们可以在(s1,s2)之间接一个不会出现的字符,这样再统计答案就可以了.
#include<bits/stdc++.h>
using namespace std;
const int N = 4e5+5;
typedef int _int;
#define int long long
int n, m, l1, l2, L[N], R[N], stk[N], top = 0, ans = 0;
int sa[N], rk[N], sec[N], buk[N], height[N];
char s1[N], s2[N], s[N];
void rsort(){
for(int i = 0; i <= m; i++) buk[i] = 0;
for(int i = 1; i <= n; i++) buk[rk[i]]++;
for(int i = 1; i <= m; i++) buk[i] += buk[i-1];
for(int i = n; i >= 1; i--) sa[buk[rk[sec[i]]]--] = sec[i];
}
void SuffixArray(){
for(int i = 1; i <= n; i++) rk[i] = s[i], sec[i] = i;
int cnt = 0; m = 300, rsort();
for(int l = 1; l <= n && cnt < n; l <<= 1){
cnt = 0;
for(int i = 1; i <= l; i++) sec[++cnt] = n-l+i;
for(int i = 1; i <= n; i++) if(sa[i] > l) sec[++cnt] = sa[i]-l;
rsort(); swap(sec, rk), rk[sa[1]] = cnt = 1;
for(int i = 2; i <= n; i++)
rk[sa[i]] = (sec[sa[i]] == sec[sa[i-1]] && sec[sa[i]+l] == sec[sa[i-1]+l]) ? cnt : ++cnt;
m = cnt;
}
}
void get_height(){
int j, k = 0;
for(int i = 1; i <= n; i++){
if(k) k--;
j = sa[rk[i]-1];
while(s[i+k] == s[j+k]) k++;
height[rk[i]] = k;
}
}
int solve(){
memset(L, 0, sizeof(L)), memset(R, 0, sizeof(R));
memset(sa, 0, sizeof(sa)), memset(rk, 0, sizeof(rk));
memset(height, 0, sizeof(height));
memset(sec, 0, sizeof(sec));
SuffixArray(), get_height();
int res = 0; stk[top = 0] = 1;
for(int i = 2; i <= n; i++){
while(top && height[stk[top]] >= height[i]) top--;
L[i] = stk[top], stk[++top] = i;
}
stk[top = 0] = n+1;
for(int i = n; i >= 2; i--){
while(top && height[stk[top]] > height[i]) top--;
R[i] = stk[top], stk[++top] = i;
}
for(int i = 2; i <= n; i++) res += height[i]*(i-L[i])*(R[i]-i);
cerr << "res=" << res << endl;
return res;
}
_int main(){
scanf("%s%s", s1+1, s2+1), l1 = strlen(s1+1), l2 = strlen(s2+1);
for(int i = 1; i <= l2; i++) s[i] = s2[i];
n = l2; ans -= solve();
for(int i = 1; i <= l1; i++) s[i] = s1[i];
n = l1; ans -= solve();
for(int i = 1; i <= l2; i++) s[i+l1+1] = s2[i];
s[l1+1] = '#', n = l1+l2+1; ans += solve();
cout << ans << endl;
return 0;
}