后缀数组-入门学习

后缀排序

Description

Tim正在自学《数据结构》，他刚刚学会如何比较两个字符串大小。书上是这么说的（和Pascal语言中的比较规则相同，学习过Pascal语言的同学可以跳过这段）：
比较两个不同字符串s1=’p1p2p3…pN’和s2=’q1q2q3…qM’的大小，设N<=M。
若s1是s2的前缀，则s1<s2。否则设pi<>qi，且i最小；若pi<qi，则s1<s2，否则s1>s2。
Tim想通过练习熟练运用这个规则，于是打算出许多字符串，并将它们从小到大排序。可是Tim非常懒，随机写出 K个很长的字符串实在是太麻烦了。不过聪明的他想到了一个好办法，他写了一个很长的字符串，自言自语说，“我只要把这个字符串的所有后缀从小到大排序就可以了”。

Input

输入文件suffix.in中仅有一行，且是一个仅包含小写字母的字符串，长度K不超过10^5。

Output

有K行，每行一个数字，第i行的数字Pi表示所有后缀中，第i小的是由原字符串第Pi个字符引导的后缀。

Sample Input

mississippi

Sample Output

11 8 5 2 1 10 9 7 4 6 3

----------------------------------------------------------------------------------------- 分割线 ------------------------------------------------------------------------------------------------------------------------------

code

#include<cstdio>
#include<cstring>
#include<cctype>
#include<cmath>
#include<set>
#include<map>
#include<list>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<vector>
#include<iostream>
#include<algorithm>
#include<stdlib.h>
#include<time.h>

using namespace std;
typedef long long LL;
const int INF=2e9+1e8;
const int MOD=1e9+7;
const int MAXSIZE=1e6+5;
const double eps=0.0000000001;
void fre()
{
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
}
#define memst(a,b) memset(a,b,sizeof(a))
#define fr(i,a,n) for(int i=a;i<n;i++)

int rankarr[MAXSIZE],wa[MAXSIZE],wb[MAXSIZE],height[MAXSIZE];
int wvarr[MAXSIZE],wsarr[MAXSIZE],SA[MAXSIZE];
char str[MAXSIZE];

int cmp(int *r,int a,int b,int l)
{
    return r[a]==r[b]&&r[a+l]==r[b+l];
}
void da(char *r,int *sa,int n,int m)
{
    int i,j,p,*x=wa,*y=wb,*t;
    for(i=0; i<m; i++) wsarr[i]=0;
    for(i=0; i<n; i++) wsarr[x[i]=r[i]]++;
    for(i=1; i<m; i++) wsarr[i]+=wsarr[i-1];
    for(i=n-1; i>=0; i--) sa[--wsarr[x[i]]]=i;
    for(j=1,p=1; p<n; j<<=1,m=p)
    {
        for(p=0,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<n; i++) wvarr[i]=x[y[i]];
        for(i=0; i<m; i++) wsarr[i]=0;
        for(i=0; i<n; i++) wsarr[wvarr[i]]++;
        for(i=1; i<m; i++) wsarr[i]+=wsarr[i-1];
        for(i=n-1; i>=0; i--) sa[--wsarr[wvarr[i]]]=y[i];
        for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1; i<n; i++)
            x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
    }
    return;
}
void calheight(char *r,int *sa,int n)
{
    int i,j,k=0;
    for(i=1; i<=n; i++) rankarr[sa[i]]=i;
    for(i=0; i<n; height[rankarr[i++]]=k)
        for(k?k--:0,j=sa[rankarr[i]-1]; r[i+k]==r[j+k]; k++);
    return;
}
int main()
{
    while(gets(str))
    {
        int n=strlen(str);
        str[n]=0;
        da(str,SA,n+1,128); //值得注意是 n+1
        calheight(str,SA,n);
        for(int i=1; i<=n; i++) printf("%d ",SA[i]);
        printf("
");
        for(int i=0; i<n; i++) printf("%d ",rankarr[i]);
        printf("
");
    }
    return 0;
}

这个字符串下标从 0~ n-1

这个代码 rank[a]=b 表示suffix(a)的排名是 b (注意:排名第一不是0,而是 1 )

所以 rank[i] 0 <= i < n

则 SA[i] 1<= i <= n

排名是1到n 数组下标是0 到 n-1。

/***
DC3 算法:
相关数组开3倍大,SA,r 数组也是。
用法与DC3 一样。末尾添加0字符，插入的特殊字符串不能和末尾
字符相同。dc3 传参数长度需要 +1 。注意int 与 char

*/


#define F(x) ((x)/3+((x)%3==1?0:tb))
#define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2)
int SA[MAXSIZE],Rank[MAXSIZE],height[MAXSIZE];
int wa[MAXSIZE],wb[MAXSIZE],wv[MAXSIZE],wss[MAXSIZE];
int c0(int *r,int a,int b)
{
    return r[a] == r[b] && r[a+1] == r[b+1] && r[a+2] == r[b+2];
}
int c12(int k,int *r,int a,int b)
{
    if(k == 2)
        return r[a] < r[b] || ( r[a] == r[b] && c12(1,r,a+1,b+1) );
    else return r[a] < r[b] || ( r[a] == r[b] && wv[a+1] < wv[b+1] );
}
void sort(int *r,int *a,int *b,int n,int m)
{
    int i;
    for(i = 0; i < n; i++)wv[i] = r[a[i]];
    for(i = 0; i < m; i++)wss[i] = 0;
    for(i = 0; i < n; i++)wss[wv[i]]++;
    for(i = 1; i < m; i++)wss[i] += wss[i-1];
    for(i = n-1; i >= 0; i--)
        b[--wss[wv[i]]] = a[i];
}
void dc3(int *r,int *sa,int n,int m)
{
    int i, j, *rn = r + n;
    int *san = sa + n, ta = 0, tb = (n+1)/3, tbc = 0, p;
    r[n] = r[n+1] = 0;
    for(i = 0; i < n; i++)if(i %3 != 0)wa[tbc++] = i;
    sort(r + 2, wa, wb, tbc, m);
    sort(r + 1, wb, wa, tbc, m);
    sort(r, wa, wb, tbc, m);
    for(p = 1, rn[F(wb[0])] = 0, i = 1; i < tbc; i++)
        rn[F(wb[i])] = c0(r, wb[i-1], wb[i]) ? p - 1 : p++;
    if(p < tbc)dc3(rn,san,tbc,p);
    else for(i = 0; i < tbc; i++)san[rn[i]] = i;
    for(i = 0; i < tbc; i++) if(san[i] < tb)wb[ta++] = san[i] * 3;
    if(n % 3 == 1)wb[ta++] = n - 1;
    sort(r, wb, wa, ta, m);
    for(i = 0; i < tbc; i++)wv[wb[i] = G(san[i])] = i;
    for(i = 0, j = 0, p = 0; i < ta && j < tbc; p++)
        sa[p] = c12(wb[j] % 3, r, wa[i], wb[j]) ? wa[i++] : wb[j++];
    for(; i < ta; p++)sa[p] = wa[i++];
    for(; j < tbc; p++)sa[p] = wb[j++];
}


void calheight(int *r,int *sa,int n)
{
    int i,j,k=0;
    for(i=1; i<=n; i++) Rank[sa[i]]=i;
    for(i=0; i<n; height[Rank[i++]]=k)
        for(k?k--:0,j=sa[Rank[i]-1]; r[i+k]==r[j+k]; k++);
    return;
}