poj 1743 Musical Theme (不可重叠最长重复子串,后缀数组)

poj 1743

题意:n个数字(1..88)表示的音符,问最长的连续两段长度至少为5的变化相同的音符段的长度。。。

思路:求最长重复字串。。。。很容易想到后缀数组。。但是这道题多了一个不可重叠的要求。

先二分答案,把题目变成判定性问题:判断是否 存在两个长度为 k 的子串是相同的,且不重叠。解决这个问题的关键还是利用 height 数组。把排序后的后缀分成若干组,其中每组的后缀之间的 height 值都 不小于 k。例如,字符串为“aabaaaab”,当 k=2 时,后缀分成了 4 组,如图 5 所示。

Selection_004

容易看出,有希望成为最长公共前缀不小于 k 的两个后缀一定在同一组。然 后对于每组后缀,只须判断每个后缀的 sa 值的最大值和最小值之差是否不小于 k。如果有一组满足,则说明存在,否则不存在。整个做法的时间复杂度为 O(nlogn)。**本题中利用 height 值对后缀进行分组的方法很常用,**请读者认真体 会。

这是论文中的题目。这个做法的确想不到,不过很好理解。

如果没有不允许重叠的条件就变成了求所有height[i]中的最大值,而每个height[i]对应的两个后缀的位置是sa[i]和sa[i-1]。

分组使得每组中的height[i]都大于等于k(那height[i]小于k的去哪里了? 因为height[i]是由两个相邻的后缀得到的,如果某两个后缀的height[i]小于k,只需要将这两个后缀分成两组,这样这个height[i]就不存在了,从而保证了每组中的height[i]都大于等于k)

而我们知道,任意两个后缀的最长公共前缀是他们之间的所有height的最小值。因为对于处于同一组内的两个后缀来说,由于之前保证了每组中的height[i]>=k,也就是保证了任意两个后缀的最长公共前缀大于等于k.

因此用二分判定长度k的时候,这样分组以后,只需要再判断是否相交(也就是如果长度k不满足,可能是因为没有办法分组使得每个height都大于等于k,也可能是存在这样的分组,但是两个后缀相交)。

判断相交其实非常简单,sa[i]表示的是排名第i的后缀的开始位置,那么如果存在sa[j]-sa[i]>=k(其实是sa[i]+k-1<sa[j],sa[i]位置开始的后缀的长度为k的前缀的最后一个字符的所在位置sa[i]+k-1比sa[j]小,就说明不相交,由于是整数,就可以变成sa[i]+k<=sa[j],也就是sa[j]-sa[i]>-=k)

而某一组内只要有一组i,j,满足sa[j]-sa[i]>=k就是有解,因此我们只需要判断最可能符合条件的一组,也就是找到一组中sa[i]的最大值和最小值,也正因为我们这样,我们在具体实现的过程中也没必要真的模拟分组的过程,只需要一直更新两个极值即可。

以及:lrj的板子是错的!!会re!!!! 已改正。

其他细节见代码注释

/* ***********************************************
Author :111qqz
Created Time :2016年07月31日 星期日 18时23分53秒
File Name :code/poj/1743.cpp
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=4E4+7;
const int C=100;
int n,sa[N],rk[N],t[N],t2[N],cnt[N];
int height[N];
int cmp(int *r ,int a,int b,int l){return r[a]==r[b]&&r[a+l]==r[b+l];}
int a[N];
void getSa( int n,int m)
{
    int *x = t;
    int *y = t2;
    ms(cnt,0);
    for ( int i = 0 ; i < n ; i++) cnt[x[i]=a[i]]++;
    for ( int i = 1 ; i < m ; i++) cnt[i]+=cnt[i-1];
    for ( int i = n-1 ; i >= 0 ; i--) sa[--cnt[x[i]]] =  i;
    for ( int k =  1 ; k <= n ; k<<=1)
    {
	int p = 0 ;
	for ( int i = n-k ; i < n ; i++) y[p++] = i ;
	for ( int i = 0 ; i < n ; i++) if (sa[i]>=k) y[p++] = sa[i]-k;
	ms(cnt,0);
	for ( int i = 0 ; i  < n ;  i++) cnt[x[y[i]]]++;
	for ( int i = 0 ; i < m ; i++) cnt[i] +=cnt[i-1];
	for ( int i = n-1 ; i >= 0 ; i--) sa[--cnt[x[y[i]]]] = y[i];
	swap(x,y);
	p = 1;
	x[sa[0]] = 0 ;
	for ( int i = 1 ; i < n; i ++)
	    x[sa[i]] = cmp(y,sa[i-1],sa[i],k)?p-1:p++;
	if (p>=n) break;
	m = p;
    }
}
void getHeight( int n)
{
    int k = 0;
    for ( int i = 0 ; i < n; i++) rk[sa[i]] = i ;
    height[0] = 0 ;
    for  ( int i = 0 ; i < n; i++)
    {
	if (rk[i]==0) continue;
	if (k) k--;
	int j = sa[rk[i]-1] ;
	while (a[i+k]==a[j+k]) k++;
	height[rk[i]] = k;
    }
}
int getSuffix( int s[],int len)
{
	int up = 0 ;
	for ( int i = 0 ; i < len ; i++)
	{
	    up = max(up,s[i]);
	}
	a[len++] = 0;
	getSa(len,up+1);
	getHeight(len);
	return len;
}
bool check( int k,int n)
{
    int mx,mn;
    mx=mn=sa[1];
   // n--;
    for ( int i = 2 ; i <= n ; i++)
    {
	if (height[i]>=k&&i<n)
	{
	    mn = min(mn,sa[i]);
	    mx = max(mx,sa[i]);
	    continue;
	}  
	if (mx-mn>=k) return true;
	mx = mn = sa[i];
    }
    return false;
}
int main()
{
	#ifndef  ONLINE_JUDGE 
	freopen("code/in.txt","r",stdin);
  #endif
	while (~scanf("%d",&n)&&n)
	{
	    for ( int i = 0 ; i < n ; i++) scanf("%d",&a[i]);
	    for ( int i = 0 ; i < n-1 ; i++) a[i] = a[i+1]-a[i]+C; //整体平移C=100,防止下标越界。
	    n--;  //是因为n个字符只有n-1个变化。
	   n = getSuffix(a,n);// 最后放了一个比所有字符都小的0(1-80+100>0),n比之前多了1
	//   for ( int i = 0 ; i <= n; i++) printf("sa[%d]:%d\n",i,sa[i]);
	    int l = 4,r = n;
	    int ans= 0 ;
	    while (l<=r)
	    {
		int mid = (l+r)/2;
		if (check(mid,n))
		{
		    ans = mid;
		    l = mid+1;
		}
		else r = mid-1;
	    }
	    ans++;  //最后再增加1是因为,5个字符虽然是4个变化,但是应该算作5个字符。等于是又变了回来。
	    printf("%d\n",ans<5?0:ans);
	}
  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;gaizheng
}