poj1743

题意：给出一段只有音高（整数表示），没有节奏的乐谱，问其中最长的曲调相同的没有重叠的两段的长度是多少。

分析：后缀数组，一定要注意，吉大的模板的nlogn算法，要初始化n=strlen(s) ＋1，另外，s，sa,rank一定要从0位置开始使用。height从1位置开始有意义。

这题是要在求出相邻音高之差之后找不重叠（无公共部分）的最长的重复出现过至少两次的串，也就是在height数组中找到一个连续段，其各项均大于d且sa数组中的对应段中最大值最小值之差要大于d。找到最大的d即可。d符合一个性质，就是小的d都满足，大的d都不满足。用二分法找分界线即可。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
usingnamespace std;

#define N 20004

int s[N], f[N];
int n, sa[N], height[N], rank[N], tmp[N], top[N];

void makesa()
{
    int i, j, len, na;
    na = (n <256?256 : n);
    memset(top, 0, na *sizeof(int));
    for (i =0; i < n; i++)
        top[rank[i] = s[i] &0xff]++;
    for (i =1; i < na; i++)
        top[i] += top[i -1];
    for (i =0; i < n; i++)
        sa[--top[rank[i]]] = i;
    for (len =1; len < n; len <<=1)
    {
        for (i =0; i < n; i++)
        {
            j = sa[i] - len;
            if (j <0)
                j += n;
            tmp[top[rank[j]]++] = j;
        }
        sa[tmp[top[0] =0]] = j =0;
        for (i =1; i < n; i++)
        {
            if (rank[tmp[i]] != rank[tmp[i -1]] || rank[tmp[i] + len]
                    != rank[tmp[i -1] + len])
                top[++j] = i;
            sa[tmp[i]] = j;
        }
        memcpy(rank, sa, n *sizeof(int));
        memcpy(sa, tmp, n *sizeof(int));
        if (j >= n -1)
            break;
    }
}

void lcp()
{
    int i, j, k;
    for (j = rank[height[i = k =0] =0]; i < n -1; i++, k++)
        while (k >=0&& s[i] != s[sa[j -1] + k])
            height[j] = (k--), j = rank[sa[j] +1];
}

bool ok(int d)
{
    int l = sa[0], r = sa[0];
    for (int i =0; i < n; i++)
    {
        if (height[i] < d)
        {
            l = sa[i];
            r = sa[i];
            continue;
        }
        if (sa[i] < l)
            l = sa[i];
        if (sa[i] > r)
            r = sa[i];
        if (r - l > d)
            returntrue;
    }
    returnfalse;
}

int binarysearch()
{
    int l =0;
    int r = n;
    while (l < r)
    {
        int mid = (l + r) /2+ ((l + r) &1);
        if (ok(mid))
            l = mid;
        else
            r = mid -1;
    }
    return l;
}

int main()
{
    //freopen("t.txt", "r", stdin);
while (scanf("%d", &n), n)
    {
        for (int i =0; i < n; i++)
            scanf("%d", &f[i]);
        for (int i =0; i < n -1; i++)
            s[i] = f[i +1] - f[i];
        makesa();
        lcp();
        int ans = binarysearch();
        if (ans >=4)
            printf("%d\n", ans +1);
        else
            printf("0\n");
    }
    return0;
}