【LOJ#3095】[SNOI2019]字符串（后缀数组）

题面

题解

首先画图看看如何比较两个串的大小，发现这个东西等价于求两个相邻的后缀的\(LCP\)。

一个做法是求出\(SA\)，然后就可以很容易的判断两个位置的大小了。

然而实际上相邻两个后缀的\(LCP\)转移可以很容易的从前一个得到，所以这部分的复杂度不会超过\(O(n)\)。

那么复杂度瓶颈就在排序了，时间复杂度\(O(nlogn)\)。

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

#define MAX 1000100

int n,p[MAX];

char A[MAX];

int LCP[MAX];

bool cmp(int a,int b)

{

	int t=1;if(a>b)t^=1,swap(a,b);

	int len=b-a;

	if(LCP[a+1]>=len)return (a>b)^t;

	return (A[a+LCP[a+1]]<A[a+1+LCP[a+1]])^t;

}

int main()

{

	scanf("%d%s",&n,A+1);

	for(int i=2;i<=n;++i)

	{

		LCP[i]=max(0,LCP[i-1]-1);

		while(i+LCP[i]<=n&&A[i+LCP[i]]==A[i+LCP[i]-1])++LCP[i];

	}

	for(int i=1;i<=n;++i)p[i]=i;

	sort(&p[1],&p[n+1],cmp);

	for(int i=1;i<=n;++i)printf("%d ",p[i]);puts("");

	return 0;

}

巴特西

【LOJ#3095】[SNOI2019]字符串（后缀数组）

【LOJ#3095】[SNOI2019]字符串（后缀数组）

题面

题解

最新文章

热门文章