BZOJ 3172 Tjoi2013 单词 后缀数组

题目大意：给定一个n个单词的文章，求每一个单词在文章中的出现次数

文章长度<=10^6(不是单词长度<=10^6,不然读入直接超时)

首先将全部单词用空格连接成一个字符串。记录每一个单词的起始位置和长度

然后求后缀数组，对于每一个单词后缀数组中一定有连续一段后缀以这个单词开头，我们通过一開始记录的起始位置找到这个单词的后缀，然后左右端点二分答案，满足左右端点之间的后缀与原单词的LCP都当与等于原单词长度就可以

时间复杂度O(nlogn)

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 1001001
using namespace std;
int n,m;
char s[M];
int st[210],len[210];
int rank[M],sa[M],height[M],X[M],Y[M];
int sum[M],cnt[M],temp[M],tot;
int min_num[M][21],log2[M];
void Get_Rank()
{
	int i;
	for(i=1;i<=m;i++)
		sum[s[i]]++;
	for(i=1;i<=127;i++)
		sum[i]+=sum[i-1];
	for(i=1;i<=m;i++)
		sa[ sum[s[i]-1]+ ++cnt[s[i]] ]=i;
	for(i=1;i<=m;i++)
	{
		if(i==1||s[sa[i]]!=s[sa[i-1]])
			++tot;
		rank[sa[i]]=tot;
	}
}
void Radix_Sort(int key[],int order[])
{
	int i;
	for(i=0;i<=m;i++)
		sum[i]=cnt[i]=0;
	for(i=1;i<=m;i++)
		sum[key[i]]++;
	for(i=1;i<=m;i++)
		sum[i]+=sum[i-1];
	for(i=1;i<=m;i++)
		temp[ sum[key[order[i]]-1]+ ++cnt[key[order[i]]] ]=order[i];
	for(i=1;i<=m;i++)
		order[i]=temp[i];
}
void Get_Height()
{
	int i,j,k;
	for(i=1;i<=m;i++)
	{
		if(rank[i]==1) continue;
		j=max(height[rank[i-1]]-1,0);k=sa[rank[i]-1];
		while(s[i+j]==s[k+j]) j++;
		height[rank[i]]=j;
	}
}
void Prefix_Doubling()
{
	int i,j;
	Get_Rank();
	for(j=1;j<=m;j<<=1)
	{
		for(i=1;i<=m;i++)
		{
			X[i]=rank[i];
			Y[i]=i+j>m?

0:rank[i+j]; sa[i]=i; } Radix_Sort(Y,sa); Radix_Sort(X,sa); for(i=1,tot=0;i<=m;i++) { if( i==1 || X[sa[i]]!=X[sa[i-1]] || Y[sa[i]]!=Y[sa[i-1]] ) ++tot; rank[sa[i]]=tot; } } Get_Height(); } void Input() { int i; char *p=s+1; for(i=1;i<=n;i++) { scanf("%s",p); st[i]=p-s; len[i]=strlen(p); *(p+=len[i],p++)=' '; } *(--p)=0; m=p-s-1; } inline int Min(int x,int y) { if(x>y) return 0x3f3f3f3f; return min( min_num[x][log2[y-x+1] ] , min_num[y-(1<<log2[y-x+1])+1][log2[y-x+1] ] ); } int Left_Bisection(int i) { int l=1,r=rank[st[i]]; while(l+1<r) { int mid=l+r>>1; if( Min(mid+1,rank[st[i]])>=len[i] ) r=mid; else l=mid; } if( Min(l+1,rank[st[i]])>=len[i] ) return l; return r; } int Right_Bisection(int i) { int l=rank[st[i]],r=m; while(l+1<r) { int mid=l+r>>1; if( Min(rank[st[i]]+1,mid)>=len[i] ) l=mid; else r=mid; } if( Min(rank[st[i]]+1,r)>=len[i] ) return r; return l; } int main() { int i,j; cin>>n; Input(); Prefix_Doubling(); log2[0]=-1; for(i=1;i<=m;i++) log2[i]=log2[i>>1]+1; for(i=1;i<=m;i++) min_num[i][0]=height[i]; for(j=1;j<=log2[m];j++) for(i=1;i+(1<<j)-1<=m;i++) min_num[i][j]=min( min_num[i][j-1] , min_num[i+(1<<j-1)][j-1] ); for(i=1;i<=n;i++) { int l=Left_Bisection(i); int r=Right_Bisection(i); printf("%d\n",r-l+1); } }