SA学习笔记

关于后缀排序这玩意应该都知道了.........

看这篇博客你可能需要一点前置知识.......建议先自行了解SA的一些定义.

梳理一下(height)数组的性质、求法以及(LCP(i,j))的求法

约定几个前置定义:

(Suffix(i)) :表示后缀(i)

(SA[i]) : 表示排名第 (i) 的后缀

(rk[i]) :表示后缀(i)的排名

(LCP(i,j)) :表示后缀(i)和后缀(j)的最长公共前缀

(str):表示的就是给出的字符串，(str[i]就表示第i个字符)

(height)数组的介绍

(height[i]表示的是排名为i的后缀与排名为i-1的后缀的最长公共前缀)。

表示出来即为 : (height[i] = LCP(SA[i],SA[i - 1]);)

(height)数组的性质:

(height[i] >= height[i - 1] - 1)(可以用来求(height数组))
对于(LCP(i,j)),不妨令(rk[i]) < (rk[j]),那么(LCP(i,j) = min(height[rk[i]+1],height[rk[i]+2],height[rk[i]+3]......height[rk[j]]))

关于上面性质的证明：后缀数组罗穗骞

这里就不再赘述了。

求(height)数组的方法:

定义h数组：(h[i] = height[ rk[i] ])。按照(h[1] , h[2] , h[3]....h[n]的顺序求解)

有一点点绕，(rk[i]表示的是后缀i排序后的排名)。

(height[rk[i]])就是当前(后缀i排序后的排名　与　后缀i排序后的排名 - 1的最长公共前缀)

我们依次遍历以(str[1])为开头的后缀，以(str[2])为开头的后缀.....以(str[3])为开头的后缀，同时求解(h[i])

放上代码来讲吧:

void GetHeight()
{
    int k=0;
    for(int i = 1 ; i <= n ; i ++)
    {
        if(k)k--;
        int j = SA[rk[i]-1];//获得排名 rk[i] - 1 的后缀的位置，i则是排名rk[i]的后缀的位置
        while(str[i + k] == str[j + k])k ++;//暴力匹配
        height[rk[i]] = k;//rk[i]表示的是后缀i的排名
    }
    return ;
}

这样子就可以求得(height)数组了

对于(LCP(i,j))的求法

我们上面写了"对于(LCP(i,j)),不妨令(rk[i]) < (rk[j]),那么(LCP(i,j) = min(height[rk[i]+1],height[rk[i]+2],height[rk[i]+3]....height[rk[j]]))"
于是这就是一个经典的,ＲＭＱ可以维护的区间最值问题了。
RMQ O((nlog(n)))预处理,O(1)查询即可　

ps.我写的这个后缀数组基本上都是写成函数的形式，方便您观看，也便于作为模板

Code

#include <bits/stdc++.h>
using namespace std;

struct Pre{
	int data,id;//预处理要用的　
} P[500005];

struct Node {
	int K1,K2,id;
} S[500005];

char a[500005];
int SA[500005],rk[500005],height[500005];
int Min[500005][25];//RMQ要用
int n ;

int cmpP(Pre A,Pre B);
int cmpN(Node A, Node B);
void Sort();//排序
bool GetRank(int x);//排序
void GetHeight();
void DealRMQ();
void prepare();
int LCP(int l,int r);//给出的函数对应下面的顺序，方便查找　

int main()
{
	prepare();//预处理以及读入
	Sort();//进行后缀排序　
	for(int i = 1 ; i <= n ; i ++)SA[rk[i]] = i;//给SA数组赋值
	GetHeight();//获得height数组
	DealRMQ();//处理RMQ
	int ans = 0;
	return 0;
}

int cmpP(Pre A,Pre B)
{
	return A.data < B.data;
}

int cmpN(Node A, Node B)
{
	if(A.K1 != B.K1)return A.K1 < B.K1;
	else return A.K2 < B.K2;
}

void Sort()
{
	int x = 1;
	while( ! GetRank(x) )x << 1;//倍增
	return ;
}

bool GetRank(int x)
{
	for(int i = 1 ; i <= n ; i ++)
	{
		S[i].K1 = rk[i];
		if(i + x > n)S[i].K2 = 0 ;
		else S[i].K2 = rk[i + x];
		S[i].id = i;
	}
	sort(S + 1 , S + 1 + n , cmpN);//没有写基排
	S[0].K1 = -1 , S[0].K2 = -1;
	int now = 0;
	for(int i = 1 ; i <= n ; i ++)
	{
		if(S[i].K1 != S[i-1].K1 || S[i].K2 != S[i-1].K2)now ++;
		rk[S[i].id] = now;
	}
	if(now == n)return 1;//如果排名都不相同，排名完毕，返回1
	else return 0;//否则返回0
}

void GetHeight()
{
	int k = 0;
	for(int i = 1 ; i <= n ; i ++)
	{
		if(k) k --;
		int j = SA[rk[i] - 1];
		while(a[j + k] == a[i + k]) k ++;
		height[rk[i]] = k;
	}
	return ;
}

void DealRMQ()
{
	for(int i = 1 ; i <= n ; i ++)Min[i][0] = height[i];
	for(int j = 1 ; j <= log2(n); j ++)
		for(int i = 1 ; i + (1 << j) - 1 <= n ; i ++)
	Min[i][j] =	min(Min[i][j-1],Min[i + (1 << (j-1))][j - 1]);
}

void prepare()
{	
	cin >> a + 1;
	n = strlen(a + 1);
	for(int i = 1 ; i <= n ; i ++)
	{
		P[i].id = i ;
		P[i].data = a[i] - 'a' + 1;
	}
	sort(P + 1 , P + 1 + n , cmpP);
	for(int i = 1 , now = 0 ; i <= n ; i ++)
	{
		if(P[i].data != P[i-1].data)now ++;
		rk[P[i].id] = now;//处理一开始的排名,给rk数组赋初值
	}
	return ;
}

int LCP(int l,int r)
{
	int Les = min(rk[l],rk[r]) + 1;
	int Gre = max(rk[l],rk[r]);
	int k = log2(Gre - Les + 1);
	return min(Min[Les][k],Min[Gre - (1 << k) + 1][k]);
}