poj1743 Musical Theme

Musical Theme

Time Limit: 1000MS		Memory Limit: 30000K
Total Submissions: 32531		Accepted: 10843

Description

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!

Input

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.

Output

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.

Sample Input

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

Sample Output

Hint

Use scanf instead of cin to reduce the read time.

Source

LouTiancheng@POJ

题目大意：有N(1 <= N <=20000)个音符的序列来表示一首乐曲，每个音符都是1..88范围内的整数，现在要找一个重复的主题。“主题”是整个音符序列的一个子串，它要满足条件：1.长度至少为5. 2.重复出现,可能整体加/减一个数. 3.重复出现的部分不能重叠.

分析：从第二个条件入手，重复出现说明什么？可以用后缀数组！Why? height数组保存的就是相邻两个后缀的LCP. 这说明通过height数组所求的答案会是重复出现的.

　　　可能整体加/减一个数该怎么处理？ ai可能变化，但是a_i+1 - ai是不会变的，也就是差分数组是不会变的，维护差分数组即可.

　　　重复出现的部分不能重叠怎么办？我一开始的想法是直接找height最大的i,看sa[i - 1]与sa[i]是否重叠. 得到的答案可能不是最优的. 　

　　　那么枚举每一个height,看sa[i-1]与sa[i]是否重叠？考虑的不够全面，height数组只考虑了相邻两个后缀的LCP.

　　　so?我们可以分组！二分出一个长度k,把height≥k并且连续的分为一组.如果中断则再分一组. 记录每一组sa的最小值和最大值，看是否重叠就可以了.
　　　height数组只考虑了相邻两个后缀的LCP.有时候会使得问题考虑的不全面. 要会这种二分+分组的方法. 将最优性问题转化为判定性问题.

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

using namespace std;

const int maxn = 30010;
int n,s[maxn],ans,fir[maxn],sec[maxn],pos[maxn],sa[maxn],rk[maxn],tong[maxn],ht[maxn];
int sett[maxn],a[maxn],cnt;

void solve()
{
    int len = n;
    memset(rk,0,sizeof(rk));
    memset(sa,0,sizeof(sa));
    memset(ht,0,sizeof(ht));
    memset(fir,0,sizeof(fir));
    memset(sec,0,sizeof(sec));
    memset(pos,0,sizeof(pos));
    memset(tong,0,sizeof(tong));
    copy(s + 1,s + len + 1,sett + 1);
    sort(sett + 1,sett + 1 + len);
    cnt = unique(sett + 1,sett + 1 + len) - sett - 1;
    for (int i = 1; i <= len; i++)
        a[i] = lower_bound(sett + 1,sett + 1 + cnt,s[i]) - sett;
    for (int i = 1; i <= len; i++)
        tong[a[i]]++;
    for (int i = 1; i <= len; i++)
        tong[i] += tong[i - 1];
    for (int i = 1; i <= len; i++)
        rk[i] = tong[a[i] - 1] + 1;
    for (int t = 1; t <= len; t *= 2)
    {
        for (int i = 1; i <= len; i++)
            fir[i] = rk[i];
        for (int i = 1; i <= len; i++)
        {
            if (i + t > len)
                sec[i] = 0;
            else
                sec[i] = rk[i + t];
        }
        fill(tong,tong + 1 + len,0);
        for (int i = 1; i <= len; i++)
            tong[sec[i]]++;
        for (int i = 1; i <= len; i++)
            tong[i] += tong[i - 1];
        for (int i = 1; i <= len; i++)
            pos[len - --tong[sec[i]]] = i;
        fill(tong,tong + 1 + len,0);
        for (int i = 1; i <= len; i++)
            tong[fir[i]]++;
        for (int i = 1; i <= len; i++)
            tong[i] += tong[i - 1];
        for (int i = 1; i <= len; i++)
        {
            int temp = pos[i];
            sa[tong[fir[temp]]--] = temp;
        }
        bool flag = true;
        int last = 0;
        for (int i = 1; i <= len; i++)
        {
            int temp = sa[i];
            if (!last)
                rk[temp] = 1;
            else if (fir[temp] == fir[last] && sec[temp] == sec[last])
            {
                rk[temp] = rk[last];
                flag = false;
            }
            else
                rk[temp] = rk[last] + 1;
            last = temp;
        }
        if (flag)
            break;
    }
    int k = 0;
    for (int i = 1; i <= len; i++)
    {
        if (rk[i] == 1)
            k = 0;
        else
        {
            if (k)
                k--;
            int j = sa[rk[i] - 1];
            while (i + k <= len && j + k <= len && a[i + k] == a[j + k])
                k++;
        }
        ht[rk[i]] = k;
    }
}

bool check(int x)
{
    int minn = sa[1],maxx = sa[1];
    for (int i = 2; i <= n; i++)
    {
        if (ht[i] >= x)
        {
            minn = min(minn,sa[i]);
            maxx = max(maxx,sa[i]);
            if (maxx - minn > x)
                return true;
            continue;
        }
        minn = maxx = sa[i];
    }
    return false;
}

int main()
{
    while (scanf("%d",&n) != EOF && n)
    {
        for (int i = 1; i <= n; i++)
            scanf("%d",&s[i]);
        for (int i = 1; i < n; i++)
            s[i] = s[i + 1] - s[i] + 100;
        n--;
        solve();
        int l = 4,r = n;
        while (l <= r)
        {
            int mid = (l + r) >> 1;
            if (check(mid))
            {
                ans = mid;
                l = mid + 1;
            }
            else
                r = mid - 1;
        }
        if (ans < 4)
            printf("%d
",0);
        else
            printf("%d
",ans + 1);
    }

    return 0;
}