<commit_before>#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
char str[1000010];
int Rank[1000010],sa[1000010];
int sum[1000010],tp[1000010];
int height[1000010],h[1000010];
void get_sa(int n)
{
    int m=127;
    for(int i=1;i<=n;i++) Rank[i]=str[i],tp[i]=i;
    for(int i=0;i<=m;i++) sum[i]=0;
    for(int i=1;i<=n;i++) sum[Rank[tp[i]]]++;
    for(int i=1;i<=m;i++) sum[i]+=sum[i-1];
    for(int i=n;i>=1;i--) sa[sum[Rank[tp[i]]]--]=tp[i];
    int p=1;
    for(int len=1;p<n;len<<=1,m=p)
    {
        p=0;
        for(int i=n-len+1;i<=n;i++) tp[++p]=i;
        for(int i=1;i<=n;i++) if(sa[i]>len) tp[++p]=sa[i]-len;
        for(int i=0;i<=m;i++) sum[i]=0;  //Rank为第一关键字，tp为第二关键字
        for(int i=1;i<=n;i++) sum[Rank[tp[i]]]++;
        for(int i=1;i<=m;i++) sum[i]+=sum[i-1];
        for(int i=n;i>=1;i--) sa[sum[Rank[tp[i]]]--]=tp[i];
        swap(Rank,tp);Rank[sa[1]]=1;p=1;
        for(int i=2;i<=n;i++)
            Rank[sa[i]]=(tp[sa[i]]==tp[sa[i-1]]&&tp[sa[i]+len]==tp[sa[i-1]+len])?p:++p;
    }
    int lst=0,j;
    for(int i=1;i<=n;h[i]=lst,height[Rank[i++]]=lst)
        for(lst=lst?lst-1:lst,j=sa[Rank[i]-1];str[j+lst]==str[i+lst];++lst);
}
int main()
{
    scanf("%s",str+1);
    int n=strlen(str+1);
    get_sa(n);
    for(int i=1;i<=n;i++)
        printf("%d ",height[i]);
    puts("");
}
<commit_msg>后缀数组 update<commit_after>#include<bits/stdc++.h>

typedef long long ll;
typedef unsigned long long ull;

using namespace std;

const int MAXN=2E6+10;

char s[MAXN];
int Rank[MAXN],sa[MAXN],tp[MAXN],buk[MAXN],n,height[MAXN];

void build_sa()
{
    int *Rk=Rank,*tmp=tp;
    int m=127;
    for(int i=1;i<=n;i++)
        Rk[i]=s[i],tmp[i]=i;
    for(int i=1;i<=m;i++)
        buk[i]=0;
    for(int i=1;i<=n;i++)
        buk[Rk[tmp[i]]]++;
    for(int i=1;i<=m;i++)
        buk[i]+=buk[i-1];
    for(int i=n;i;i--)
        sa[buk[Rk[tmp[i]]]--]=tmp[i];
    int p=1;
    for(int len=1;p<n;m=p,len<<=1)
    {
        p=0;
        for(int i=n-len+1;i<=n;i++)
            tmp[++p]=i;
        for(int i=1;i<=n;i++)
            if(sa[i]-len>0)
                tmp[++p]=sa[i]-len;
        for(int i=1;i<=m;i++)
            buk[i]=0;
        for(int i=1;i<=n;i++)
            buk[Rk[tmp[i]]]++;
        for(int i=1;i<=m;i++)
            buk[i]+=buk[i-1];
        for(int i=n;i;i--)
            sa[buk[Rk[tmp[i]]]--]=tmp[i];
        swap(Rk,tmp);
        Rk[sa[1]]=p=1;
        for(int i=2;i<=n;i++)
            Rk[sa[i]]=(tmp[sa[i]]==tmp[sa[i-1]]&&tmp[sa[i]+len]==tmp[sa[i-1]+len])?p:++p;
    }
    for(int i=1;i<=n;i++)
        Rank[sa[i]]=i;
    for(int i=1,j=0;i<=n;height[Rank[i++]]=j)
        for(j=j?j-1:j;s[i+j]==s[sa[Rank[i-1]]+j];j++);
}

int main()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    build_sa();
    for(int i=1;i<=n;i++)
        printf("%d%c",sa[i],"\n "[i!=n]);
}

{'fraction_non_alphanumeric': 0.28396694214876034, 'fraction_numerical': 0.04033057851239669, 'mean_word_length': 3.185338865836791, 'pattern_counts': {'":': 0, '<': 46, '<?xml version=': 0, '>': 19, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1646658', 'n_tokens_mistral': 1561, 'n_tokens_neox': 1503, 'n_words': 185}