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

柔情只为你懂 2021-11-24 00:28 239阅读 0赞

2014-6-23 更新

使用DC3模板重写了这题，同时尝试不借助vector对height数组进行分组，效率提升很明显，代码附在最后。

原来的写法 4668K 344MS

现在的写法 996K235MS

不过原来借助vector分组相对更好理解。

—————————— 分割线 ——————————

这道题也是 USACO5.1.3，据说Poj数据较弱，但是在USACO交题需要先把前面的好多题刷完……

楼教主男人八题之一

网上的有一些代码是有问题的，详见下面的分析和代码最后的数据，不过在Poj上有问题也能过。

我是在Poj的讨论版里看到的 http://poj.org/showmessage?message\_id=181597

题意：有N个音符的序列来表示一首乐曲，每个音符都是1..88范围内的整数，现在要找一个重复的主题。“主题”是整个音符序列的一个子串，它需要满足如下条件：

1.长度至少为5个音符。

2.在乐曲中重复出现。(可能经过转调，“转调”的意思是主题序列中每个音符都被加上或减去了同一个整数值)

3.重复出现的同一主题不能有公共部分。

思路：很容易想到对原序列做差。但是与各种题解、论文上所述不同的是，求的是相距至少为一的最长重复序列，而不仅仅是不重叠的最长重复序列。

因为做差之后的序列中，每一项代表原先相邻的两项。

比如这个数据：1 2 3：作差后得到 1 1.这里第一个1是指(1 2)，第二个一是指(2 3)，如果选择它们作为两个序列，这就重复了。

POJ上的数据弱，查不出这一点来。但是交到USACO上就看出来了。

同样的原因，最后序列的长度应该加1。

具体解法：

后缀数组+二分答案

对于一个二分的值K，判断可行的方法：

因为某一个height\[i\]对应的是sa\[i\]和sa\[i-1\]的lcp，按照Hight数组 >= K 对排序后的SA数组进行分组（实现见代码），保证后缀数组SA中的一段L - R , 若Height \[ L + 1 \] ~ Height \[ R \] 全部大于等于K，那么就等价于第L到第R个后缀中任意两个后缀的LCP值都大于等于K。

借用 [后缀数组两种算法的分析比较 - Localhost 8080 - C++博客][- Localhost 8080 - C] 中的一张图

![SouthEast][]

那么只要取每组里相隔最远的两个后缀，若他们相距大于L，那么就是可行的(实现方法：由SA数组定义，判断同一个分组内最大值和最小值之差是否大于k)。

注：本题求的是相距至少为一的最长重复序列，若求不重叠的最长重复序列，只需同一个分组内最大值和最小值之差不小于k即可。

#include <cstdio>
    #include <cstring>
    #include <cstdlib>
    #include <algorithm>
    #include <vector>
    using namespace std;
    #define max(a,b) ((a)>(b)?(a):(b))
    #define min(a,b) ((a)<(b)?(a):(b))
    
    const int N = int(2e5)+10;
    
    int cmp(int *r,int a,int b,int l){
        return (r[a]==r[b]) && (r[a+l]==r[b+l]);
    }
    int wa[N],wb[N],ws[N],wv[N];
    int rank[N],height[N];
    
    void DA(int *r,int *sa,int n,int m){
        int i,j,p,*x=wa,*y=wb,*t;
        for(i=0;i<m;i++) ws[i]=0;
        for(i=0;i<n;i++) ws[x[i]=r[i]]++;
        for(i=1;i<m;i++) ws[i]+=ws[i-1];
        for(i=n-1;i>=0;i--) sa[--ws[x[i]]]=i;
        for(j=1,p=1;p<n;j*=2,m=p)
        {
            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]];
            for(i=0;i<m;i++) ws[i]=0;
            for(i=0;i<n;i++) ws[wv[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];
            for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
                x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
            //printf("p = %d\n", p );
        }
    }
    void calheight(int *r,int *sa,int n){
      //  memset(height,0,sizeof(height));
      //  memset(rank,0,sizeof(rank));
        int i,j,k=0;
        for(i=1;i<=n;i++) rank[sa[i]]=i;
        for(i=0;i<n; height[rank[i++]] = k )
        for(k?k--:0,j=sa[rank[i]-1]; r[i+k]==r[j+k]; k++);
    }
    
    int data[N], sa[N], n;
    
    vector<int> S[N];
    
    bool Judge (int k)
    {
    	bool flag = false;
    	int i,cur = -1;
    	for (i=1;i<=n;i++)   //分组
    	{
    		if (height[i] < k)
    			S[++cur].clear();
    		S[cur].push_back(i);
    	}
    	for (i=1;i<=cur;i++)
    	{
    		int Max=-1,Min=N;
    		if (S[i].size() > 1)
    		{
    			for (int j=0;j<S[i].size();j++)
    			{
    				Max = max( Max, sa[ S[i][j] ] );
    				Min = min( Min, sa[ S[i][j] ] );
    			}
    			if ( Max-Min > k ) //严格大于
    			{
    				flag = true; 
    				break;
    			}
    		}
    	}
    	return flag;
    }
    
    int Deal ()
    {
    	DA(data,sa,n+1,200);
    	calheight(data,sa,n);
    	int low=0,high=n,mid,ans=-1;
    	while (low<high)   //注意二分的写法
    	{
    		mid = (low+high)>>1;
    		if ( Judge(mid) )
    			ans=mid,low=mid+1;
    		else high = mid;
    	}
    	return ans>=4?ans+1:0;
    }
    
    int main ()
    {
    	while (scanf("%d",&n),n)
    	{
    		int i;
    		for (i=0;i<n;i++)
    			scanf("%d",&data[i]);
    		for (i=0;i<n-1;i++)
    			data[i]=data[i+1]-data[i]+90;  //由于要用基数排序,+90以防出现负数
    		data[--n]=0;
    		printf("%d\n",Deal());
    	}
    	return 0;
    }
    /*
    Input
    1
    2
    9
    1 1 1 1 1 1 1 1 1
    30
    25 27 30 34 39 45 52 60 69 79 69 60 52 45 39 34 30 26 22 18
    82 78 74 70 66 67 64 60 65 80
    0
    
    Out
    0
    0
    5
    */

#include <cstdio>
    #include <cstring>
    #define max(a,b) ((a)>(b)?(a):(b))
    #define min(a,b) ((a)<(b)?(a):(b))
    
    const int N = int(2e4)+10;
    
    #define F(x) ((x)/3+((x)%3==1?0:tb))
    #define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2)
    
    int wa[N],wb[N],wv[N],ws[N];
    int c0 (int *r,int a,int b){
    	return r[a]==r[b] && r[a+1]==r[b+1] && r[a+2]==r[b+2];
    }
    int c12 (int k,int *r,int a,int b){
    	if (k==2) return r[a]<r[b] || r[a]==r[b] && c12(1,r,a+1,b+1);
    	else return r[a]<r[b] || r[a]==r[b] && wv[a+1]<wv[b+1];
    }
    void sort (int *r,int *a,int *b,int n,int m){
    	int i;
    	for(i=0;i<n;i++) wv[i]=r[a[i]];
    	for(i=0;i<m;i++) ws[i]=0;
    	for(i=0;i<n;i++) ws[wv[i]]++;
    	for(i=1;i<m;i++) ws[i]+=ws[i-1];
    	for(i=n-1;i>=0;i--) b[--ws[wv[i]]]=a[i];
    }
    void DC3 (int *r,int *sa,int n,int m){
    	int i,j,*rn=r+n,*san=sa+n,ta=0,tb=(n+1)/3,tbc=0,p;
    	r[n]=r[n+1]=0;
    	for(i=0;i<n;i++) if(i%3!=0) wa[tbc++]=i;
    	sort(r+2,wa,wb,tbc,m);
    	sort(r+1,wb,wa,tbc,m);
    	sort(r,wa,wb,tbc,m);
    	for(p=1,rn[F(wb[0])]=0,i=1;i<tbc;i++)
    		rn[F(wb[i])]=c0(r,wb[i-1],wb[i])?p-1:p++;
    	if(p<tbc) DC3(rn,san,tbc,p);
    	else for(i=0;i<tbc;i++) san[rn[i]]=i;
    	for(i=0;i<tbc;i++) if(san[i]<tb) wb[ta++]=san[i]*3;
    	if(n%3==1) wb[ta++]=n-1;
    	sort(r,wb,wa,ta,m);
    	for(i=0;i<tbc;i++) wv[wb[i]=G(san[i])]=i;
    	for(i=0,j=0,p=0;i<ta && j<tbc;p++)
    		sa[p]=c12(wb[j]%3,r,wa[i],wb[j])?wa[i++]:wb[j++];
    	for(;i<ta;p++) sa[p]=wa[i++];
    	for(;j<tbc;p++) sa[p]=wb[j++];
    }  
    int rank[N],height[N],data[3*N],sa[3*N];
    
    void calheight(int *r,int *sa,int n){
    //	memset(height,0,sizeof(height));
    //	memset(rank,0,sizeof(rank));
    	int i,j,k=0;
    	for(i=1;i<=n;i++) rank[sa[i]]=i;
    	for(i=0;i<n; height[rank[i++]] = k )
    	for(k?k--:0,j=sa[rank[i]-1]; r[i+k]==r[j+k]; k++);
    }
    
    int n;
    
    bool Judge (int k)
    {
    	int up=sa[1],down=sa[1];
    	for (int i=2;i<=n;i++) //hight[1]没意义,因为sa[0]存的是结束符
    		if (height[i]<k)
    			up=down=sa[i];
    		else
    		{
    			up=max(up,sa[i]);
    			down=min(down,sa[i]);
    			if (up-down > k) //严格大于
    				return true;
    		}
        return false;
    }
    
    int Deal ()
    {
    	DC3(data,sa,n+1,200);
    	calheight(data,sa,n);
    	int low=0,high=n,mid,ans=-1;
    	while (low<high)   //注意二分的写法
    	{
    		mid = (low+high)>>1;
    		if ( Judge(mid) )
    			ans=mid,low=mid+1;
    		else high = mid;
    	}
    	return ans>=4?ans+1:0;
    }
    
    int main ()
    {
    	while (scanf("%d",&n),n)
    	{
    		int i;
    		for (i=0;i<n;i++)
    			scanf("%d",&data[i]);
    		for (i=0;i<n-1;i++)
    			data[i]=data[i+1]-data[i]+90;  //由于要用基数排序,+90以防出现负数
    		data[--n]=0;
    		printf("%d\n",Deal());
    	}
    	return 0;
    }
    /*
    Input
    1
    2
    9
    1 1 1 1 1 1 1 1 1
    30
    25 27 30 34 39 45 52 60 69 79 69 60 52 45 39 34 30 26 22 18
    82 78 74 70 66 67 64 60 65 80
    0
    
    Out
    0
    0
    5
    */

[- Localhost 8080 - C]: http://www.cppblog.com/superKiki/archive/2010/05/15/115421.html
[SouthEast]: /images/20211122/c7a08f76dac74eb8a69ac62a974c79bf.png