4566: [Haoi2016]找相同字符

Time Limit: 20 Sec  Memory Limit: 256 MB

Submit: 275  Solved: 155

[][][]

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 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;const int N=4e5+5;typedef long long ll;inline int read(){    char c=getchar();int x=0,f=1;    while(c<'0'||c>'9'){
    if(c=='-')f=-1; c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();}    return x*f;}int n,d[N];char s[N];struct State{    int ch[26],par,val;}t[N];int sz,root,last;inline int nw(int _){t[++sz].val=_;return sz;}inline void iniSAM(){sz=0;root=last=nw(0);}void extend(int c){    int p=last,np=nw(t[p].val+1); d[np]=1;     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+1) t[np].par=q;        else{            int nq=nw(t[p].val+1);            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=0;i<=n;i++) c[i]=0;     for(int i=1;i<=sz;i++) c[t[i].val]++;    for(int i=1;i<=n;i++) c[i]+=c[i-1];    for(int i=sz;i>=1;i--) a[c[t[i].val]--]=i; }int appear[N];ll ans,f[N];void solve(){    iniSAM();    scanf("%s",s+1);n=strlen(s+1);    for(int i=1;i<=n;i++) extend(s[i]-'a');    RadixSort();    int u;    for(int i=sz;i>=1;i--)        u=a[i],d[t[u].par]+=d[u];    int len=0;u=root;    scanf("%s",s+1);n=strlen(s+1);    for(int i=1;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+1,u=t[u].ch[c];        }        appear[u]++,ans+=(ll)d[u]*(len-t[t[u].par].val);    }    for(int i=sz;i>=1;i--)        u=a[i],f[t[u].par]+=f[u]+appear[u];    for(int i=2;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();}