首页 > 代码库 > HDOJ 5008 Boring String Problem

HDOJ 5008 Boring String Problem

2024-10-08 11:11:39   214人阅读


后缀数组+RMQ+二分

后缀数组二分确定第K不同子串的位置 , 二分LCP确定可选的区间范围 , RMQ求范围内最小的sa

Boring String Problem

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 661    Accepted Submission(s): 183


Problem Description
In this problem, you are given a string s and q queries.

For each query, you should answer that when all distinct substrings of string s were sorted lexicographically, which one is the k-th smallest. 

A substring si...j of the string s = a1a2 ...an(1 ≤ i ≤ j ≤ n) is the string aiai+1 ...aj. Two substrings sx...y and sz...w are cosidered to be distinct if sx...y ≠ Sz...w
 

Input
The input consists of multiple test cases.Please process till EOF. 

Each test case begins with a line containing a string s(|s| ≤ 105) with only lowercase letters.

Next line contains a postive integer q(1 ≤ q ≤ 105), the number of questions.

q queries are given in the next q lines. Every line contains an integer v. You should calculate the k by k = (l⊕r⊕v)+1(l, r is the output of previous question, at the beginning of each case l = r = 0, 0 < k < 263, “⊕” denotes exclusive or)
 

Output
For each test case, output consists of q lines, the i-th line contains two integers l, r which is the answer to the i-th query. (The answer l,r satisfies that sl...r is the k-th smallest and if there are several l,r available, ouput l,r which with the smallest l. If there is no l,r satisfied, output “0 0”. Note that s1...n is the whole string)
 

Sample Input
aaa
4
0
2
3
5
 

Sample Output
1 1
1 3
1 2
0 0
 

Source
2014 ACM/ICPC Asia Regional Xi‘an Online
 



#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

typedef long long int LL;

const int maxn=110100;
const int INF=0x3f3f3f3f;

int sa[maxn],rank[maxn],rank2[maxn],h[maxn],c[maxn],
	*x,*y,ans[maxn];
char str[maxn];

bool cmp(int* r,int a,int b,int l,int n)
{
	if(r[a]==r[b]&&a+l<n&&b+l<n&&r[a+l]==r[b+l])
		return true;
	return false;
}

void radix_sort(int n,int sz)
{
	for(int i=0;i<sz;i++) c[i]=0;
	for(int i=0;i<n;i++) c[x[y[i]]]++;
	for(int i=1;i<sz;i++) c[i]+=c[i-1];
	for(int i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];
}

void get_sa(char c[],int n,int sz=128)
{
	x=rank,y=rank2;
	for(int i=0;i<n;i++) x[i]=c[i],y[i]=i;
	radix_sort(n,sz);
	for(int len=1;len<n;len<<=1)
	{
		int yid=0;
		for(int i=n-len;i<n;i++) y[yid++]=i;
		for(int i=0;i<n;i++) if(sa[i]>=len) y[yid++]=sa[i]-len;

		radix_sort(n,sz);

		swap(x,y);
		x[sa[0]]=yid=0;

		for(int i=1;i<n;i++)
		{
			x[sa[i]]=cmp(y,sa[i],sa[i-1],len,n)?yid:++yid;
		}
		sz=yid+1;
		if(sz>=n) break;
	}
	for(int i=0;i<n;i++) rank[i]=x[i];
}

void get_h(char str[],int n)
{
	int k=0; h[0]=0;
	for(int i=0;i<n;i++)
	{
		if(rank[i]==0) continue;
		k=max(k-1,0);
		int j=sa[rank[i]-1];
		while(i+k<n&&j+k<n&&str[i+k]==str[j+k]) k++;
		h[rank[i]]=k;
	}
}

LL Range[maxn];

int bin(LL x,int n)
{
	int ans=-1;
	int low=0,high=n-1,mid;
	while(low<=high)
	{
		mid=(low+high)/2;
		if(Range[mid]<x)
		{
			ans=mid;
			low=mid+1;
		}
		else
		{
			high=mid-1;
		}
	}
	return ans;
}

int lcp[maxn][20],mmm[maxn][20];

void RMQ_init(int n)
{
	for(int i=0;i<n;i++)
	{
		lcp[i][0]=h[i];
		mmm[i][0]=sa[i];
	}
	lcp[0][0]=0x3f3f3f3f;
	int sz=floor(log(n*1.0)/log(2.0));
	for(int i=1;(1<<i)<=n;i++)
	{
		for(int j=0;j+(1<<i)-1<n;j++)
		{
			lcp[j][i]=min(lcp[j][i-1],lcp[j+(1<<(i-1))][i-1]);
			mmm[j][i]=min(mmm[j][i-1],mmm[j+(1<<(i-1))][i-1]);
		}
	}
}

int LCP(int l,int r,int n)
{
	if(l==r) return n-sa[l];
	l++;
	if(l>r) swap(l,r);
	int k=0;
	while(1<<(k+1)<=r-l+1) k++;
	return min(lcp[l][k],lcp[r-(1<<k)+1][k]);
}

int MMM(int l,int r)
{
	if(l>r) swap(l,r);
	int k=0;
	while(1<<(k+1)<=r-l+1) k++;
	return min(mmm[l][k],mmm[r-(1<<k)+1][k]);
}

int binID(int x,int n,int len)
{
	int ans=x;	
	int low=x,high=n-1,mid;
	while(low<=high)
	{
		mid=(low+high)/2;
		if(LCP(x,mid,n)>=len)
		{
			ans=mid;
			low=mid+1;
		}
		else high=mid-1;
	}
	return ans;
}
int main()
{
while(scanf("%s",str)!=EOF)
{
	int n=strlen(str);
	get_sa(str,n);
	get_h(str,n);
	RMQ_init(n);
	for(int i=0;i<n;i++)
	{
		Range[i]=(n-sa[i])-h[i];
		if(i-1>=0) Range[i]+=Range[i-1];
	}
	int q;
	scanf("%d",&q);
	int L=0,R=0;
	LL V;
	while(q--)
	{
		scanf("%I64d",&V);
		LL K=(L^R^V)+1LL;
		if(K>Range[n-1])
		{
			L=0;R=0;
			printf("%d %d\n",L,R);
			continue;
		}
		int id=bin(K,n);
		LL jian=0;
		if(id>=0) jian=Range[id];
		LL res=K-jian; id++;
		int len=h[id]+res;	
		int hid=binID(id,n,len);
		int Left=MMM(id,hid);	
		printf("%d %d\n",Left+1,Left+len);
		L=Left+1;R=Left+len;
	}
}
	return 0;
}


HDOJ 5008 Boring String Problem


联系
我们