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

描述

A musical melody is represented as a sequence of N (1<=N<=20000)notes that are integers in the range 1..88, each representing a key on the piano. It is unfortunate but true that this representation of melodies ignores the notion of musical timing; but, this programming task is about notes and not timings.

Many composers structure their music around a repeating &qout;theme&qout;, which, being a subsequence of an entire melody, is a sequence of integers in our representation. A subsequence of a melody is a theme if it:

is at least five notes long

appears (potentially transposed — see below) again somewhere else in the piece of music

is disjoint from (i.e., non-overlapping with) at least one of its other appearance(s)

Transposed means that a constant positive or negative value is added to every note value in the theme subsequence.

Given a melody, compute the length (number of notes) of the longest theme.

One second time limit for this problem’s solutions!

输入

The input contains several test cases. The first line of each test case contains the integer N. The following n integers represent the sequence of notes.
The last test case is followed by one zero.

输出

For each test case, the output file should contain a single line with a single integer that represents the length of the longest theme. If there are no themes, output 0.

样例

输入

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

输出

5

题意

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

如果存在长度至少为5个音符的子串，则输出最长的子串的长度，否则输出0

思路

首先贴一下罗穗骞大佬的论文里的做法

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

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

说实话我当时根本没看懂大佬所表达的意思，尤其是这个分组，我现在也没看懂why。我是看了别人的博客以后又错了无数发才写出来的···

记录一下我对这个题的理解

首先要清楚sa[]所表达的意思 “排第几的是谁?”

看图：

height[]是在sa[]的基础上所求出来的

height[i]表示sa[i]与sa[i-1]所对应的字符串的最长公共前缀

（这也是在代码中每次进行判断不重叠的原理）

mm=min(mm,min(sa[i],sa[i-1]));
mx=max(mx,max(sa[i],sa[i-1]));
if(mx-mm>k) return 1;
// sa[i]的值为sa[i]所对应的字符串首字母在原串中的位置
// 因为题目要求不重叠，因此需要(mx-mn>k)即两个首字母的位置大于k，这样才不会重叠。可以结合配图，在纸上试一下，理解了这个这个题就不难了

最难的部分说完了，剩下的就是对输入的处理了，由于有这么一个要求（可能经过转调，“转调”的意思是主题序列中每个音符都被加上或减去了同一个整数值），因此要找到一个方法巧妙的处理这个问题。

举个栗子：1 2 3 4 —> 7 8 9 10(1 2 3 4 经过转调以后，变为7 8 9 10）。但是不难发现，无论它如何转调，他们的相对差值是不会变的，因此我们处理一下将数据改为它与前一位数的差值，便解决了。

代码

/*
 * =============================================
 *
 *       Filename:  A.cpp
 *
 *           Link:  http://poj.org/problem?id=1743
 *
 *        Version:  1.0
 *        Created:  2018/10/01 15时23分10秒
 *       Revision:  none
 *       Compiler:  g++
 *
 *         Author:  杜宁元 (https://duny31030.top/), duny31030@126.com
 *   Organization:  QLU_浪在ACM
 *
 * =============================================
 */
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define clr(a, x) memset(a, x, sizeof(a))
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define pre(i,a,n) for(int i=n;i>=a;i--)
#define ll long long
#define max3(a,b,c) fmax(a,fmax(b,c))
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int MAXN = 2e6+10;;

int wa[MAXN],wb[MAXN],wv[MAXN],ws[MAXN];
int cmp(int *r,int a,int b,int l)
{
    return r[a]==r[b] && r[a+l]==r[b+l];
}
int sa[MAXN],rk[MAXN],height[MAXN];
void SA(int *r,int n,int m)
{
    int *x=wa,*y=wb;

    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=n-1; i>=0; --i) sa[--ws[x[i]]]=i;

    int p=1;
    for(int j=1; p<n; j<<=1,m=p)
    {
        p=0;
        for(int i=n-j; i<n; ++i) y[p++]=i;
        for(int i=0; i<n; ++i) if(sa[i]>=j) y[p++]=sa[i]-j;
        for(int i=0; i<n; ++i) wv[i]=x[y[i]];
        for(int i=0; i<m; ++i) ws[i]=0;
        for(int i=0; i<n; ++i) ++ws[wv[i]];
        for(int i=1; i<m; ++i) ws[i]+=ws[i-1];
        for(int i=n-1; i>=0; --i) sa[--ws[wv[i]]]=y[i];
        swap(x,y); x[sa[0]]=0; p=1;
        for(int i=1; i<n; ++i) x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
    }

    for(int i=1; i<n; ++i) rk[sa[i]]=i;
    int k=0;
    for(int i=0; i<n-1; height[rk[i++]]=k)
    {
        if(k) --k;
        for(int j=sa[rk[i]-1]; r[i+k]==r[j+k]; ++k);
    }
}

int n,a[MAXN],r[MAXN];

bool ok(int k)
{
    int mx = -INF,mn = INF;
    // height[1] 没意义  i从2开始
    for(int i = 2;i <= n;i++)
    {
        if(height[i] >= k)
        {
            mn = min(mn,min(sa[i],sa[i-1]));
            mx = max(mx,max(sa[i],sa[i-1]));
            if(mx-mn>k)
                return true;
        }
        else
            mx = -INF,mn = INF;
    }
    return false;
}


int main()
{
#ifdef ONLINE_JUDGE
#else
        freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
#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++)
            r[i] = a[i+1]-a[i]+88;
        r[n-1] = 0;
        SA(r,n,176);
        int l = 0,r = n;
        while(l < r)
        {
            int mid = (l+r+1)>>1;
            if(ok(mid))
                l = mid;
            else
                r = mid-1;
        }
        if(l >= 4)
            printf("%d
",l+1);
        else
            printf("0
");
    }
    fclose(stdin);
    // fclose(stdout);
    return 0;
}