SA字尾數組模闆 檔案修複

記數排序

void ssort()
{
    memset(a,,sizeof(a));
    int mx=;fo(i,,n) a[x[y[i]]]++,mx=max(mx,x[y[i]]);
    fo(i,,mx) a[i]+=a[i-];
    for(int i=n;i>;i--) sa[a[x[y[i]]]]=y[i],a[x[y[i]]]--;
}
           

求SA和rank

x為排序後的字元串，y為排序第二關鍵字，sa[i]為排第i是什麼，rank[i]為第i排第幾

height[i]為sa[i]和sa[i-1]的最長公共字首

void getsa()
{
    fo(i,,n) y[i]=i,x[i]=s[i];ssort();
    for(int j=;j<=n;j*=)
    {
        int k=;fo(i,n-j+,n) y[++k]=i;
        fo(i,,n) if (sa[i]>j) y[++k]=sa[i]-j;
        ssort();
        fo(i,,n) y[i]=x[i],x[i]=;
        x[sa[]]=;k=;
        fo(i,,n)
        {
            if (y[sa[i]]!=y[sa[i-]] || y[sa[i]+j]!=y[sa[i-]+j]) k++;
            x[sa[i]]=k;
        }
        if (k==n) break;
    }
    fo(i,,n) rank[sa[i]]=i;
}
           

求height

void getheight()
{
    int k=;
    fo(i,,n)
    {
        int j=sa[rank[i]-];
        while (i+k<=n && j+k<=n && s[i+k]==s[j+k]) k++;
        height[rank[i]]=k;
        if (k>) k--;
    }
}
           

完整代碼

題目：檔案修複

求字元串中至少出現兩次的個數

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <cstdlib>
#include <iostream>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define N 101000
using namespace std;
int n,i,j,k,a[N],sa[N],rank[N],height[N],x[N],y[N];
char s[N];
void ssort()
{
    memset(a,,sizeof(a));
    int mx=;fo(i,,n) a[x[y[i]]]++,mx=max(mx,x[y[i]]);
    fo(i,,mx) a[i]+=a[i-];
    for(int i=n;i>;i--) sa[a[x[y[i]]]]=y[i],a[x[y[i]]]--;
}
void getsa()
{
    fo(i,,n) y[i]=i,x[i]=s[i];ssort();
    for(int j=;j<=n;j*=)
    {
        int k=;fo(i,n-j+,n) y[++k]=i;
        fo(i,,n) if (sa[i]>j) y[++k]=sa[i]-j;
        ssort();
        fo(i,,n) y[i]=x[i],x[i]=;
        x[sa[]]=;k=;
        fo(i,,n)
        {
            if (y[sa[i]]!=y[sa[i-]] || y[sa[i]+j]!=y[sa[i-]+j]) k++;
            x[sa[i]]=k;
        }
        if (k==n) break;
    }
    fo(i,,n) rank[sa[i]]=i;
}
void getheight()
{
    int k=;
    fo(i,,n)
    {
        int j=sa[rank[i]-];
        while (i+k<=n && j+k<=n && s[i+k]==s[j+k]) k++;
        height[rank[i]]=k;
        if (k>) k--;
    }
}
int main()
{
    scanf("%s",s+);n=strlen(s+);
    getsa();getheight();
    int ans=;
    fo(i,,n) if (height[i]>height[i-]) ans=ans+height[i]-height[i-];
    printf("%d",ans);
}