2019/5/14 day3 解题日志

2019-05-14

字数统计: 1.7k字 | 阅读时长: 9分

给串$A$和$B$，求有多少组$(la,ra,lb,rb)$，使得$A[la..ra] = B[lb..rb]$。

题目链接

day3

$O(n^2)$

如果能够满足$O(n^2)$的算法，可以用以下方法做。

字符串hash + map

先对A和B进行hash预处理。
首先枚举相同子串长度len，遍历A的所有长度为len的子串，得到hash值，并且用map进行记录个数。
然后再到B串里进行相应统计便可。整体复杂度是$O(n^2logn)$的。

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int maxn=2e5+10;
char s[maxn],t[maxn];
unordered_map<ull,int>mp;
ull base = 131;
ull po[maxn],hs[maxn],ht[maxn];
ull geth(ull *hs1,int l,int r){return (ull)hs1[r]-po[r-l+1]*hs1[l-1];}
int main(){
    po[0]=1;
    for(int i=1;i<=200000;i++)po[i]=po[i-1]*base;
    scanf("%s%s",s+1,t+1);
    int n=strlen(s+1),m=strlen(t+1);
    ull ans=0;
    for(int i=1;i<=n;i++)hs[i]=hs[i-1]*base+s[i];
    for(int i=1;i<=m;i++)ht[i]=ht[i-1]*base+t[i];
    for(int i=1;i<=n;i++){
        mp.clear();
        for(int bg=1;bg+i-1<=n;bg++)mp[geth(hs,bg,bg+i-1)]++;
        for(int bg=1;bg+i-1<=m;bg++){
            ans+=mp[geth(ht,bg,bg+i-1)];
        }
    }cout<<ans;
    return 0;
}

后缀数组

首先对$S=A+dollor+B$的字符串进行后缀排序，处理出height数组。
我们知道$lcp(suf_i,suf_j) = min(height[i+1],height[i+2]..height[j]) $。
假如$suf_i$是A串的后缀，那么从$i+1$开始遍历，并维护$lcp$便可求出$suf_i$对答案的贡献。
需要枚举$i$和遍历$i$之后的所有后缀，$lcp$可以$O(1)$维护，复杂度$O(n^2)$。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 4e5+10;
struct SA{
    int rk[maxn],sa[maxn],height[maxn];
    int t1[maxn],t2[maxn],c[maxn];
    bool cmp(int *s,int a,int b,int l){
        return s[a]==s[b]&&s[a+l]==s[b+l];
    }
    void Sa(char *s,int n,int m){
        n++;
        int i,j,p,*x=t1,*y=t2;
        for(i=0;i<m;i++)c[i]=0;
        for(i=0;i<n;i++)c[x[i]=s[i]]++;
        for(i=1;i<m;i++)c[i]+=c[i-1];
        for(i=n-1;i>=0;i--)sa[--c[x[i]]]=i;
        for(j=1;j<=n;j<<=1){
            p=0;
            for(i=n-j;i<n;i++)y[p++]=i;
            for(i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;
            for(i=0;i<m;i++)c[i]=0;
            for(i=0;i<n;i++)c[x[y[i]]]++;
            for(i=1;i<m;i++)c[i]+=c[i-1];
            for(i=n-1;i>=0;i--)sa[--c[x[y[i]]]]=y[i];
            swap(x,y);
            p=1;x[sa[0]]=0;
            for(i=1;i<n;i++)x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
            if(p>=n)break;m=p;
        }
        int k=0;n--;
        for(i=0;i<=n;i++)rk[sa[i]]=i;
        for(i=0;i<n;i++){
            if(k)k--;
            j=sa[rk[i]-1];
            while(s[i+k]==s[j+k])k++;
            height[rk[i]]=k;
        }
    }
    void solven2(int n,int len1){
        int ans=0;
        for(int i=1;i<=n;i++){
            if(sa[i]<len1){
                int lcp=maxn;
                for(int j=i+1;j<=n;j++){
                    lcp=min(lcp,height[j]);
                    if(!lcp)break;
                    if(sa[j]>=len1)ans+=lcp;
                }
                continue;
            }
            int lcp=maxn;
            for(int j=i+1;j<=n;j++){
                lcp=min(lcp,height[j]);
                if(!lcp)break;
                if(sa[j]<len1)ans+=lcp;
            }
        }cout<<ans;
    }
}sa;
char s1[maxn],s2[maxn];
int len1,len2;
char s[maxn];
int main(){
    scanf("%s%s",s1,s2);
    len1=strlen(s1);len2=strlen(s2);
    int n=0;
    for(int i=0;i<len1;i++)s[n++]=s1[i];
    s[n++]='$';
    for(int i=0;i<len2;i++)s[n++]=s2[i];
    s[n]=0;
    sa.Sa(s,n,128);
    sa.solven2(n,len1);
    return 0;
}

$O(n)$

后缀数组+单调栈

前文提到的后缀数组方法有一个硬伤，就是需要枚举每一个后缀，能不能只用一次循环就维护出贡献呢？这里可以运用前缀和的思想以及单调栈来维护。
由于存在性质：$lcp(suf_i,suf_j) = min(height[i+1],height[i+2]..height[j]) $，所以对于$suf_i$而言，每个$suf_j$的贡献是越来越小的，也就是说满足单调性。

那么考虑如何维护这个前缀和。假设栈内当前每个后缀贡献长度为$a$，此时对于$suf_j$，贡献为$min(height[j],a)$。如果$height[j] \lt a$，前面所有的后缀贡献都会被更新为$height[j]$，否则，分开算贡献即可。

复杂度分析：$O(nlogn)$的预处理和$O(n)$的求值，整体$O(nlogn)$。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 4e5+10;
char s1[maxn],s2[maxn];
int len1,len2;
pair<int,ll> stk[maxn];
struct SA{
    int rk[maxn],sa[maxn],height[maxn];
    int t1[maxn],t2[maxn],c[maxn];
    bool cmp(int *s,int a,int b,int l){
        return s[a]==s[b]&&s[a+l]==s[b+l];
    }
    void Sa(char *s,int n,int m){
        n++;
        int i,j,p,*x=t1,*y=t2;
        for(i=0;i<m;i++)c[i]=0;
        for(i=0;i<n;i++)c[x[i]=s[i]]++;
        for(i=1;i<m;i++)c[i]+=c[i-1];
        for(i=n-1;i>=0;i--)sa[--c[x[i]]]=i;
        for(j=1;j<=n;j<<=1){
            p=0;
            for(i=n-j;i<n;i++)y[p++]=i;
            for(i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;
            for(i=0;i<m;i++)c[i]=0;
            for(i=0;i<n;i++)c[x[y[i]]]++;
            for(i=1;i<m;i++)c[i]+=c[i-1];
            for(i=n-1;i>=0;i--)sa[--c[x[y[i]]]]=y[i];
            swap(x,y);
            p=1;x[sa[0]]=0;
            for(i=1;i<n;i++)x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
            if(p>=n)break;m=p;
        }
        int k=0;n--;
        for(i=0;i<=n;i++)rk[sa[i]]=i;
        for(i=0;i<n;i++){
            if(k)k--;
            j=sa[rk[i]-1];
            while(s[i+k]==s[j+k])k++;
            height[rk[i]]=k;
        }
    }
    void solven2(int n,int len1){
        int ans=0;
        for(int i=1;i<=n;i++){
            if(sa[i]<len1){
                int lcp=maxn;
                for(int j=i+1;j<=n;j++){
                    lcp=min(lcp,height[j]);
                    if(!lcp)break;
                    if(sa[j]>=len1)ans+=lcp;
                }
                continue;
            }
            int lcp=maxn;
            for(int j=i+1;j<=n;j++){
                lcp=min(lcp,height[j]);
                if(!lcp)break;
                if(sa[j]<len1)ans+=lcp;
            }
        }cout<<ans;
    }
    void solve(int n){
        ll ret=0;
        int sum[maxn];sum[0]=0;
        for(int i=1;i<=n;i++)sum[i]=sum[i-1]+(sa[i]<len1);
        int top=0;
        stk[0]=make_pair(1,0);
        for(int i=1;i<=n;i++){
            while(top &&height[ stk[top].first ]>height[i])top--;++top;
            stk[top]=make_pair(i,(sum[i-1]-sum[stk[top-1].first-1])*height[i]+stk[top-1].second);
            if(sa[i]>len1)ret+=stk[top].second;
        }top=0;
        for(int i=1;i<=n;i++)sum[i]=sum[i-1]+(sa[i]>len1);
        for(int i=1;i<=n;i++){
            while(top &&height[ stk[top].first ]>height[i])top--;top++;
            stk[top]=make_pair(i,(sum[i-1]-sum[stk[top-1].first-1])*height[i]+stk[top-1].second);
            if(sa[i]<len1)ret+=stk[top].second;
        }cout<<ret;
    }
}sa;

char s[maxn];
int main(){
    scanf("%s%s",s1,s2);
    len1=strlen(s1);len2=strlen(s2);
    int n=0;
    for(int i=0;i<len1;i++)s[n++]=s1[i];
    s[n++]='$';
    for(int i=0;i<len2;i++)s[n++]=s2[i];
    s[n]=0;
    sa.Sa(s,n,128);
    sa.solve(n);
    //sa.solven2(n,len1);
    return 0;
}

后缀自动机+DP

留坑。