题解 CF204E 【Little Elephant and Strings】

· · 题解

SA+单调队列

首先转化成SA可以解决的问题：对于每一个字符串的每一个后缀，我们找出来自 k 个不同字符串的后缀，使得它们的 LCP 最大，然后这个字符串的答案加上 LCP的大小

相当于在统计答案 (l,r) 的个数时，对于每个字符串的每一个 l ，求出 r 最大是多少，然后该字符串的答案加上 r-l+1

因此按照套路，我们把这 n 个字符串首尾相接，并且为了防止跨越字符串的子串影响答案，需要在每两个字符中间插入一个间隔符，并且需要两两不同

我们发现LCP有一个很好的性质：对于两个后缀i、j，它们在 SA 中的距离越远，LCP就越短（结合 “ LCP 是由 Height 数组取区间最小值求得的 ” 可以形象理解）

所以，我们找到的 k 个后缀在SA数组中的排名必须尽可能与该后缀 “近”

如何量化这个 “近” 呢？

我们找出SA数组上所有 “ 包含恰好 k 个不同字符串中的后缀 ” 的区间，求出这个区间的LCP 作为它的 “价值” ，这样一个后缀的答案就一定在所有包含它的区间中（因为如果包含了大于k个，那么这些后缀一定离它 “ 不够近 ” ），取max即可

用双指针维护，并把这些区间塞到一个vector里，结合维护过程可以得知这样的区间只有O(N)个（N表示字符串长度和）

然后对于SA数组中的每一个位置求出对应的答案，由于vector里的区间满足左右端点都随着下标递增而单调不降（因为是双指针维护出来的），所以可以抽象成一个区间求max，单调队列维护即可

复杂度O(N\log N)+O(N)+O(N)=O(N\log N)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200005;
int n,m,k;
int sa[N],rk[N],tmp[N<<1],cnt[N],h[N];
int a[N];
int st[N][20],lg[N];
void SA(){
    int i,j,num=m+200;
    for(i=1;i<=n;i++) cnt[rk[i]=a[i]]++;
    for(i=2;i<=num;i++) cnt[i]+=cnt[i-1];
    for(i=1;i<=n;i++) sa[++cnt[rk[i]-1]]=i;
    for(j=1;j<n;j<<=1){
        for(i=0;i<=num;i++) cnt[i]=0;
        for(i=1;i<=n;i++) cnt[rk[i]]++;
        for(i=2;i<=num;i++) cnt[i]+=cnt[i-1];
        for(i=n-j+1;i<=n;i++) tmp[++cnt[rk[i]-1]]=i;
        for(i=1;i<=n;i++)
            if(sa[i]>j) tmp[++cnt[rk[sa[i]-j]-1]]=sa[i]-j;
        for(i=1;i<=n;i++) sa[i]=tmp[i];
        for(i=1;i<=n;i++) tmp[i]=rk[i];
        num=0;
        for(i=1;i<=n;i++)
            rk[sa[i]]=((tmp[sa[i]]==tmp[sa[i-1]]&&tmp[sa[i]+j]==tmp[sa[i-1]+j])?num:++num);
    }
    for(i=1;i<=n;i++){
        if(rk[i]==1) continue;
        h[rk[i]]=max(h[rk[i-1]]-1,0);
        int x=sa[rk[i]-1];
        while(i+h[rk[i]]<=n&&a[i+h[rk[i]]]==a[x+h[rk[i]]]) h[rk[i]]++;
    }
    for(i=1;i<=n;i++) st[i][0]=h[i];
    for(j=1;(1<<j)<n;j++){
        for(i=1;i+(1<<j)-1<=n;i++)
            st[i][j]=min(st[i][j-1],st[i+(1<<j-1)][j-1]);
    }
}
string s[N];
int len[N];
int pos[N];
ll ans[N];
inline int qmin(int l,int r){
    if(l>r) return len[sa[r]];
    int len=lg[r-l+1];
    return min(st[l][len],st[r-(1<<len)+1][len]);
}
int q[N],hd,tl;
struct seg{
    int l,r,w;
    inline seg(int l,int r,int w):l(l),r(r),w(w){}
};
vector<seg> v;
int main(){
    int i,j;
    cin>>m>>k;//我设n为字符串总长，m为字符串个数
    lg[1]=0;for(i=2;i<N;i++) lg[i]=lg[i-1]+(1<<lg[i-1]+1==i);
    for(i=1;i<=m;i++){
        cin>>s[i];int l=s[i].length();
        for(j=0;j<l;j++){
            a[++n]=s[i][j]-'a'+m;
            pos[n]=i;len[n]=l-j;
        }
        a[++n]=i;
    }
    a[n--]=0;
    SA();//求SA,Height
    memset(cnt,0,sizeof(cnt));
    int p=m,ck=0;
    //循环变量从m开始是因为前m-1个一定是分隔符打头，没有意义
    for(i=m;i<=n;i++){//预处理区间以及价值
        int x=pos[sa[i]];//注意枚举顺序是sa[1]~sa[n]，而不是1~n
        if(!cnt[x]) ck++;
        cnt[x]++;
        while(ck>=k){
            if(ck==k) v.push_back(seg(p,i,qmin(p+1,i)));
            if(cnt[pos[sa[p]]]==1){
                if(ck==k) break;
                ck--;
            }
            cnt[pos[sa[p]]]--;p++;
        }
    }
//  for(auto x:v) cout<<x.l<<" "<<x.r<<" "<<x.w<<endl;
    p=0;
    for(i=m;i<=n;i++){//单调队列统计答案
        while(hd<tl&&v[q[hd]].r<i) hd++;
        while(p<v.size()&&v[p].l<=i){
            while(hd<tl&&v[p].w>=v[q[tl-1]].w) tl--;
            q[tl++]=p;
            p++;
        }
        if(hd==tl) continue;
        ans[pos[sa[i]]]+=v[q[hd]].w;
    }
    for(i=1;i<=m;i++) cout<<ans[i]<<" ";
    return 0;
}