[Codechef TASTR] Level of Difference

Description

给定两个字符串，求恰好在一个字符串中出现过的本质不同的子串数量。

Solution

设 \(U(S)\) 表示在 \(S\) 中出现过的本质不同的子串集合，那么答案集合 \(A\)

\[A = U(P) + U(Q) - 2 U(P) \cap U(Q)
\]

\[|A| = |U(P)| + |U(Q)| - 2 |U(P) \cap U(Q)|
\]

根据容斥原理

\[U(P) \cap U(Q) = U(P) + U(Q) - U(P) \cup U(Q)
\]

于是

\[|A| = 2 |U(P) \cup U(Q)| - U(P) - U(Q)
\]

#include <bits/stdc++.h>

using namespace std;

#define int long long

struct sa

{

    int n,m=256,sa[1000005],y[1000005],u[1000005],v[1000005],o[1000005],r[1000005],h[1000005],T;

    char str[1000005];

    long long ans;

    int cal()

    {

        memset(sa,0,sizeof sa);

        memset(y,0,sizeof y);

        memset(u,0,sizeof u);

        memset(v,0,sizeof v);

        memset(o,0,sizeof o);

        memset(r,0,sizeof r);

        memset(h,0,sizeof h);

        n=strlen(str+1);

        for(int i=1; i<=n; i++) u[str[i]]++;

        for(int i=1; i<=m; i++) u[i]+=u[i-1];

        for(int i=n; i>=1; i--) sa[u[str[i]]--]=i;

        r[sa[1]]=1;

        for(int i=2; i<=n; i++) r[sa[i]]=r[sa[i-1]]+(str[sa[i]]!=str[sa[i-1]]);

        for(int l=1; r[sa[n]]<n; l<<=1)

        {

            memset(u,0,sizeof u);

            memset(v,0,sizeof v);

            memcpy(o,r,sizeof r);

            for(int i=1; i<=n; i++) u[r[i]]++, v[r[i+l]]++;

            for(int i=1; i<=n; i++) u[i]+=u[i-1], v[i]+=v[i-1];

            for(int i=n; i>=1; i--) y[v[r[i+l]]--]=i;

            for(int i=n; i>=1; i--) sa[u[r[y[i]]]--]=y[i];

            r[sa[1]]=1;

            for(int i=2; i<=n; i++) r[sa[i]]=r[sa[i-1]]+((o[sa[i]]!=o[sa[i-1]])||(o[sa[i]+l]!=o[sa[i-1]+l]));

        }

        {

            int i,j,k=0;

            for(int i=1; i<=n; h[r[i++]]=k)

                for(k?k--:0,j=sa[r[i]-1]; str[i+k]==str[j+k]; k++);

        }

        ans=(long long)n*(long long)(n+1)/(long long)2;

        for(int i=1; i<=n; i++) ans-=(long long)h[i];

        return ans;

    }

} sa1,sa2,sa3;

char s1[1000005],s2[1000005];

int l1,l2;

signed main()

{

    scanf("%s",s1+1);

    scanf("%s",s2+1);

    l1=strlen(s1+1);

    l2=strlen(s2+1);

    memcpy(sa1.str,s1,sizeof s1);

    memcpy(sa2.str,s2,sizeof s2);

    for(int i=1; i<=l1; i++) sa3.str[i]=s1[i];

    sa3.str[l1+1]='$';

    for(int i=1; i<=l2; i++) sa3.str[i+l1+1]=s2[i];

    cout<<2ll*(sa3.cal()-(l1+1)*(l2+1))-sa1.cal()-sa2.cal()<<endl;

}

巴特西

[Codechef TASTR] Level of Difference - 后缀数组,容斥原理

[Codechef TASTR] Level of Difference

Description

Solution

最新文章

热门文章