ADASTRNG - Ada and Substring 题解

题目描述

给定一个小写字符串。

输出 \(26\) 个数，代表以 \(\texttt{a}\sim \texttt{z}\) 开头的本质不同的子串个数。

题目分析

高度数组模板题。

可以想到将以每个字符开头的本质不同的子串数目转化为：

• 以每个字符开头的所有字串数目减去以每个字符开头的相同子串数目。

那么对于以每一个字符开头的后缀，它与排名比它上一位的后缀同时产生的子串个数即是它们的最长公共前缀长度，那么用高度数组去重就可以去掉重复产生的子串的个数。

那么每次发现该后缀与排名比它前一位的后缀都是以同一个字符开头时，直接将这个字符的答案减去 \(Height_i\) 即可。

（这道题不知道为什么，反正没有卡 \(O(nlog^2n)\) 的后缀数组求解。）

代码

/*
 * @Author: Ehundategh
 * @Date: 2023-10-25 18:17:02
 * @FilePath: \Code\LuieGu\ADASTRNG - Ada and Substring.cpp
 * @Description: You Steal,I kill
 */
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 2000010
using namespace std;
int Sa[MAXN],Rank[MAXN],Temp[MAXN],n,k=1;
long long Ans[MAXN];
int Height[MAXN];
char In[MAXN];
bool cmpsa(int i,int j){
    if(Rank[i]!=Rank[j]) return Rank[i]<Rank[j];
    else{
        int Secondi=i+k<=n?Rank[i+k]:-1;
        int Secondj=j+k<=n?Rank[j+k]:-1;
        return Secondi<Secondj;
    }
}
void Get_Sa(){
    for(int i=1;i<=n;i++) Sa[i]=i,Rank[i]=In[i];
    for(k=1;k<=n;k*=2){
        sort(Sa+1,Sa+n+1,cmpsa);
        Temp[Sa[1]]=1;
        for(int i=1;i<=n;i++) Temp[Sa[i+1]]=Temp[Sa[i]]+(cmpsa(Sa[i],Sa[i+1])?1:0);
        for(int i=1;i<=n;i++) Rank[i]=Temp[i];
    }
}
void Get_Height(){
    Height[1]=0;
    for(int i=1,k=0;i<=n;i++){
        if(Rank[i]==1) continue;
        if(k>0)k--;
        while(In[i+k]==In[Sa[Rank[i]-1]+k]) k++;
        Height[Rank[i]]=k;
    }
}
int main(){
    scanf("%s",In+1);
    n=strlen(In+1); Get_Sa(); Get_Height();
    for(int i=1;i<=n;i++){
        Ans[In[i]-'a'+1]+=1ll*(n-i+1);
    }
    for(int i=2;i<=n;i++){
        if(In[Sa[i]]==In[Sa[i-1]]) Ans[In[Sa[i]]-'a'+1]-=1ll*(Height[i]);
    }
    for(int i=1;i<=26;i++) printf("%lld ",Ans[i]);
    return 0; 
}