4566: [Haoi2016]找相同字符
Time Limit: 20 Sec Memory Limit: 256 MB
Submit: 275 Solved: 155
[Submit][Status][Discuss]
Description
给定两个字符串，求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。两个方案不同当且仅当这两
个子串中有一个位置不同。
Input
两行，两个字符串s1，s2，长度分别为n1，n2。1 <=n1, n2<= 200000，字符串中只有小写字母
Output
输出一个整数表示答案
一看两个串就是一个建SAM另一个跑
跑到状态s，贡献为|Right(s)|*(len-Min(s)+1) 也就是|Right(s)|*[len-Max(Parent(s))] 出现次数*不同串长度
并且出现次数向父亲传递，s的Parent Tree祖先也匹配了，贡献为|Right(v)|*[Max(v)-Min(v)+1]
于是我们先计算Right集合大小，然后跑的时候维护当前公共长度len，到一个状态实时更新自己(因为需要len)，然后记录下访问次数，最后倒着递推用这些访问次数更新祖先就行了
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=4e5+;
typedef long long ll;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-; c=getchar();}
while(c>=''&&c<=''){x=x*+c-''; c=getchar();}
return x*f;
}
int n,d[N];
char s[N];
struct State{
int ch[],par,val;
}t[N];
int sz,root,last;
inline int nw(int _){t[++sz].val=_;return sz;}
inline void iniSAM(){sz=;root=last=nw();}
void extend(int c){
int p=last,np=nw(t[p].val+); d[np]=;
for(;p&&!t[p].ch[c];p=t[p].par) t[p].ch[c]=np;
if(!p) t[np].par=root;
else{
int q=t[p].ch[c];
if(t[q].val==t[p].val+) t[np].par=q;
else{
int nq=nw(t[p].val+);
memcpy(t[nq].ch,t[q].ch,sizeof(t[q].ch));
t[nq].par=t[q].par;
t[q].par=t[np].par=nq;
for(;p&&t[p].ch[c]==q;p=t[p].par) t[p].ch[c]=nq;
}
}
last=np;
}
int c[N],a[N];
void RadixSort(){
for(int i=;i<=n;i++) c[i]=;
for(int i=;i<=sz;i++) c[t[i].val]++;
for(int i=;i<=n;i++) c[i]+=c[i-];
for(int i=sz;i>=;i--) a[c[t[i].val]--]=i;
}
int appear[N];
ll ans,f[N];
void solve(){
iniSAM();
scanf("%s",s+);n=strlen(s+);
for(int i=;i<=n;i++) extend(s[i]-'a'); RadixSort();
int u;
for(int i=sz;i>=;i--)
u=a[i],d[t[u].par]+=d[u]; int len=;u=root;
scanf("%s",s+);n=strlen(s+);
for(int i=;i<=n;i++){
int c=s[i]-'a';
if(t[u].ch[c]) len++,u=t[u].ch[c];
else{
while(u&&!t[u].ch[c]) u=t[u].par;
if(!u) u=root, len = 0;
else len=t[u].val+,u=t[u].ch[c];
}
appear[u]++,ans+=(ll)d[u]*(len-t[t[u].par].val);
}
for(int i=sz;i>=;i--)
u=a[i],f[t[u].par]+=f[u]+appear[u];
for(int i=;i<=sz;i++) ans+=(ll)d[i]*f[i]*(t[i].val-t[t[i].par].val);
printf("%lld",ans);
}
int main(){
freopen("in","r",stdin);
solve();
}