后缀数组

Dear 丶 2021-11-22 15:26 268阅读 0赞

#include<bits/stdc++.h>
    using namespace std;
    const int M=1e6+50;
    string s;
    int x[M],y[M],c[M],sa[M],rk[M];//sa第i名的后缀是从第sa[i]个字母开始的，rk是第i名的后缀的位置是多少
    void getsa(){
    	for(int i=1;i<=n;i++)++c[x[i]=s[i]];//入桶，某个字母有多少个
    	for(int i=2;i<=m;i++)c[i]+=c[i-1];//每个字母开头的后缀的最大可能的序列是多少 
    	for(int i=n;i;i--)sa[c[x[i]]--]=i; //对每个字母进行排序。也就是第一关键字
    	for(int k=1;k<=n;k<<=1){
    		int num=0;//这个字母的大小为0
    		for(int i=n-k-1;i<=n;i++)y[++num] =i;//有些后缀没有第二关键字，所以在最前面
    		for(int i=1;i<=n;i++)if(sa[i]>k)y[++num]=sa[i]-k;//y[]存放的是两个关键字的首位置
    		for(int i=1;i<=m;i++)c[i]=0;//清空桶 
    		for(int i=1;i<=n;i++)++c[x[i]]//数出第一关键字的首字母有多少个
    		for(int i=2;i<=m;i++)c[i]+=c[i-1]; //第一个关键字的首字母为..有多少个
    		for(int i=n;i;i--)sa[c[x[y[i]]]--]=y[i],y[i]=0;//c[x[y[i]]]是对应字符串的的首字母应该有的在所有后缀中的名次。 清空这个y[i] 
    	 	swap(x,y);
    	 	//生成下一次的第一关键字，也就是x数组，下标是x的位置，值是x大小
    		//在k为1的时候，x是第一关键字的x字母。是按照字母进行排序的，同一个字母的在一个桶里面
    		x[sa[1]]=1;//位置为sa[1]的排名是1 
    		num=1;
    		for(int i=2;i<=n;i++)
    			x[sa[i]]=(y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k])?num:++num;
    			//生成第一关键关键字的桶。相邻两个后缀，在本次排序之前是在一个桶里面的，那么这次还在一个桶里面，否则在另一个桶里面 
    		if(num==n)break;//恰好有n个桶 
    		m=num; //设置新的桶的数量 
    	} 
    	
    }