题解 P3181 【[HAOI2016]找相同字符】
totorato
2018-01-25 20:46:31
# 找相同字符 ([HAOI2016、luogu3181)
## 题意：
给定两个由小写字母组成的字符串s1,s2(长度小于等于$2\times 10^4$)。求两个字符串各取一个子串，两子串相等的方案数。
## 分析:
$O(n^3)$：
首先，我们知道。如果连个串中各取一个极长的相同的子串(极长的意思就是这两个串再向两边延伸就会不同或出界)，则这个极长的串的所有子串也是相同的。
由于枚举极长的串并求出其长度并不方便，所以我们可以枚举这个极长的串的左端点，再求出其长度。这样就可以不重不漏找出所有的极长的串。更图方便的话，我们可以只考虑两原串中某后缀的所有前缀，这可以补充不漏找出所有的子串。但是由于我们要在两个字符串中枚举，同时找出子串的长度也要话费$O(n)$的代价，固总时间复杂度是$O(n^3)$的。
$O(n^2)$:
刚才说道了后缀的前缀，我们不由自主想到了后缀数组。如果我们可以很快求出A串和B串的某两个后缀的最长公共前缀，我们就可以将时间复杂度优化的更低。所以我们可以将两个字符串通过一个分隔符拼接起来，求出Height数组，即按字典序排序后每个后缀和前一个的LCP。再利用Height数组和ST表，我们就可以$O(1)$得到任意两后缀的LCP。因此，这样做的时间复杂度只有枚举子串起点的复杂度了，即$O(n^2)$。
$O(nlogn)$：
现在拉高时间复杂度的罪魁祸首就是枚举起点了。所以我们想将其复杂度降低。考虑到利用Height数组求任意两个后缀的LCP时的独特性质：两个后缀的LCP为字典序排序后他们中间夹的最小的Height。也就是说排序后，一个后缀越往后数LCP的长度越小。
这样，我们就可以用单调栈维护这个最小值。分A串的子串在前、B的子串在前两种情况分别用单调栈求出答案，加起来就行。至于如何维护，聪明的大家一定已经知道了。
由于利用了单调栈这个神奇的手段,时间复杂度降到了$O(nlogn)$。如果我们在构建后缀数组的时候采用DC3算法，我们甚至可以在线性时间内解决这道题。(当然我还是懒得打)
```cpp
#include <iostream>
#include <cstring>
#include <cstdio>
#define MX 823123
using namespace std;
typedef long long ll;
typedef struct tSA
{
int str[MX],n,m;
int rank[MX],SA[MX],het[MX];
int buk[MX],yp[MX];
bool cmp(int *f,int x,int y,int w){return f[x]==f[y]&&f[x+w]==f[y+w];}
void jsort()
{
for(int i=0;i<=m;i++)buk[i]=0;
for(int i=1;i<=n;i++)buk[rank[yp[i]]]++;
for(int i=1;i<=m;i++)buk[i]+=buk[i-1];
for(int i=n;i>=1;i--)SA[buk[rank[yp[i]]]--]=yp[i];
}
void getSA()
{
for(int i=1;i<=n;i++)rank[i]=str[i],yp[i]=i;
m=28;jsort();
for(int w=1;w<n;w<<=1)
{
int p=0;
for(int i=n-w+1;i<=n;i++)yp[++p]=i;
for(int i=1;i<=n;i++)if(SA[i]>w)yp[++p]=SA[i]-w;
jsort(),swap(rank,yp),rank[SA[1]]=p=1;
for(int i=2;i<=n;i++)rank[SA[i]]=(cmp(yp,SA[i],SA[i-1],w)?p:++p);
m=p;
}
int k=0;
for(int i=1;i<=n;i++)
{
k=(k?k-1:0);
while(str[i+k]==str[SA[rank[i]-1]+k])k++;
het[rank[i]]=k;
}
}
}SA;
SA sa;
char str[MX];
int l1,l2,top,sum[MX];
pair<int,ll>stk[MX];
void work()
{
ll ans=0;
stk[0]=make_pair(1,0);
for(int i=1;i<=sa.n;i++)sum[i]=sum[i-1]+(sa.SA[i]<=l1);
for(int i=1;i<=sa.n;i++)
{
while(top&&sa.het[stk[top].first]>sa.het[i])top--;
top++;
stk[top]=make_pair(i,(sum[i-1]-sum[stk[top-1].first-1])*sa.het[i]+stk[top-1].second);
if(sa.SA[i]>l1+1)ans+=stk[top].second;
}
top=0;
for(int i=1;i<=sa.n;i++)sum[i]=sum[i-1]+(sa.SA[i]>l1+1);
for(int i=1;i<=sa.n;i++)
{
while(top&&sa.het[stk[top].first]>sa.het[i])top--;
top++;
stk[top]=make_pair(i,(sum[i-1]-sum[stk[top-1].first-1])*sa.het[i]+stk[top-1].second);
if(sa.SA[i]<=l1)ans+=stk[top].second;
}
printf("%lld\n",ans);
}
int main()
{
scanf("%s",str+1);l1=strlen(str+1);
scanf("%s",str+l1+2);
str[l1+1]='z'+1;
sa.n=strlen(str+1);
for(int i=1;i<=sa.n;i++)sa.str[i]=str[i]-'a'+1;
sa.getSA();
work();
return 0;
}
```