poj 1743 Musical Theme（最长重复子串后缀数组）

有N(1 <= N <=20000)个音符的序列来表示一首乐曲，每个音符都是1..88范围内的整数，现在要找一个重复的主题。“主题”是整个音符序列的一个子串，它需要满足如下条件：1.长度至少为5个音符。2.在乐曲中重复出现(可能经过转调，“转调”的意思是主题序列中每个音符都被加上或减去了同一个整数值)。3.重复出现的同一主题不能有公共部分。

首先把序列差分一下，那么现在，问题就转换成了：给定一个字符串，求最长重复子串，这两个子串不能重叠。

先来看看最长可重叠重复子串吧。首先，一对极长重复子串必定可以表示为两个后缀的LCP。同时，任意两个后缀的LCP也必定对应一对极长重复子串。它们是满射的关系。因此最长可重叠重复子串的长度相当于任意一对后缀的lcp中最长的，显然就是最大的height。

那这个做法如何推广到最长不可重叠后缀呢？我们可以发现，只有当两个后缀的距离大于它们的lcp时，才能被纳入计算。在这种情况下，我们不能保证height中的最大值一定是答案，有可能最优值的两个后缀之间隔了多个后缀。做法是二分子串长度L，将后缀数组分成若干组，每个组内的height都大于L。记录组内位置最小的，位置最大的串，看看它们之间的距离是否大于子串长度。如果是这样的，那么mid=l+1，否则mid=r。

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int maxn=4e4+5;

int n, m, a[maxn];

int *x, *y, *t, wa[maxn], wb[maxn], ws[maxn], wv[maxn], sa[maxn], ht[maxn];

int cmp(int *r, int a, int b, int l){

	return r[a]==r[b]&&r[a+l]==r[b+l]; }

void da(int *r){

	x=wa; y=wb; m=maxn;

	for (int i=0; i<m; ++i) ws[i]=0;

	for (int i=0; i<n; ++i) ++ws[x[i]=r[i]];

	for (int i=1; i<m; ++i) ws[i]+=ws[i-1];

	for (int i=0; i<n; ++i) sa[--ws[r[i]]]=i;  //sa数组必须排好序

	int i, j, p=0;

	for (j=1; j<n&&p<n; j<<=1, m=p+1){  //p代表当前倍增情况下有多少不同的后缀 m应当变成p+1

		for (p=0, i=n-j; i<n; ++i) y[p++]=i;

		for (i=0; i<n; ++i) if (sa[i]>=j) y[p++]=sa[i]-j;

		for (i=0; i<n; ++i) wv[i]=x[y[i]];  //wv:第二关键词中排i的数，在第一关键词中排第几

		for (i=0; i<m; ++i) ws[i]=0;

		for (i=0; i<n; ++i) ++ws[x[i]];  //ws:第一关键词中排名为i的数，总排名的范围是多少

		for (i=1; i<m; ++i) ws[i]+=ws[i-1];

		for (i=n-1; i>=0; --i) sa[--ws[wv[i]]]=y[i];

		t=x; x=y; y=t; x[sa[0]]=1;

		for (p=1, i=1; i<n; ++i)  //rank必须从1开始以区分空串

			x[sa[i]]=cmp(y, sa[i-1], sa[i], j)?p:++p;

	}

	memset(ht, 0, sizeof(ht));

	for (i=0; i<n; ++i) --x[i]; p=0;

	for (i=0; i<n; ht[x[i++]]=p){  //枚举原串中1到n的所有后缀

		if (!x[i]) continue;

		for (p?p--:0, j=sa[x[i]-1]; r[i+p]==r[j+p]&&i+p<n; ++p);  //p表示h[i]

	}

	return;

}

int main(){

	while (~scanf("%d", &n)&&n){

		for (int i=0; i<n; ++i) scanf("%d", &a[i]);

		for (int i=0; i<n; ++i) a[i]=a[i+1]-a[i]+88; --n;

		da(a); int l=0, r=n, k, flag;

		while (l<r){

			k=(l+r)>>1; flag=0;

			int minm=sa[0], maxm=sa[0];

			for (int i=1; i<=n; ++i){

				if (ht[i]<k){

					if (maxm-minm>k) flag=1;

					minm=sa[i]; maxm=sa[i]; continue;

				}

				minm=min(minm, sa[i]);

				maxm=max(maxm, sa[i]);

			}

			if (flag) l=k+1; else r=k;

		}

		printf("%d\n", l<5?0:l);

	}

	return 0;

}

巴特西

poj 1743 Musical Theme（最长重复子串后缀数组）

poj 1743 Musical Theme（最长重复子串后缀数组）

最新文章

热门文章

巴特西

poj 1743 Musical Theme（最长重复子串 后缀数组）

poj 1743 Musical Theme（最长重复子串 后缀数组）

最新文章

热门文章

poj 1743 Musical Theme（最长重复子串后缀数组）

poj 1743 Musical Theme（最长重复子串后缀数组）