题目链接：http://poj.org/problem?id=1743
题目大意：给你一段长度为(1<=n<=20000)的音符：每个音符是1…88范围内的整数，每个音符代表钢琴上的一个键，

一个旋律的子序列满足下面三个条件：

1.是至少五个音符长
2.在音乐片段的其他地方再次出现（可能转换 - 见下文）
3.与其至少一个其他外观不相交（即，不重叠）

转换:将恒定的正值或负值添加到主题子序列中的每个音符值。


这个题不能直接对数进行哈希，因为可能同时加减了一个数。但是相邻两个数的差是不变的，所以要对差进行哈希。

然后二分长度。对每个长度再枚举子串，再左右查询，是否存在这个字符串，对于一个长度，有n个子串，对于每个子串，每次查询都是O(n)的复杂度。二分log你个长度，时间复杂度：O（n* n *logn）

1<=n<=20000肯定T了。但是：你会发现：枚举和查询是有重复的地方，这次枚举这个串，之前查询过。其实我们可把枚举和查询合并。

用map

每次二分出长度Len。从i=0开始，得到一个长度为n的字符串，得到哈希值，r如果map[hash]=0，然后加入map[hash]=i, 如果map[hash]!=0说明之前已经出现过这个字符串，但是题目要求两个子串不重叠，

这个时候我们只有判断 i - map[hash]>=Len?如果是，那么说明两个字符串的距离>=Len一定不会重叠。
时间复杂度：O(nlognlogn)然后还是T，我现在已经无法优化了。

TLE:
#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int maxn=20006;

ull base =131;
ull g[maxn];
ull p[maxn];
int n;

int a[20005], b[20005];

ull Hash(int s[], int n)
{
    ull ans=0;

    g[0]=s[0];
    for(int i=1;i<n;i++)
    {
        g[i]=g[i-1]*base+s[i];
    }
    return g[n-1];
}

void getp()
{
    p[0]=1;
    for(int i=1;i<=maxn;i++)
    {
        p[i]=p[i-1]*base;
    }
}

ull getLR(int l, int r)//取出T里l - r里面的字符串的hash值
{
    return g[r]-g[l-1]*p[r-l+1];
}

map<ull, int> mp;
int dfs(int Len)
{
    mp.clear();
    for(int i=1;i<=n-Len+1;i++)
    {
        ull now=getLR(i, i+Len-2);
        int k=mp[now];
        if(k)
        {
            if(i-k>=Len)
            {
                return 1;
            }
        }
        else
        {
            mp[now]=i;
        }
    }
    return 0;
}

int main()
{
    getp();
    while(scanf("%d",&n),n)
    {
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        for(int i=1;i<n;i++)
        {
            b[i]=a[i+1]-a[i];
        }
        Hash(b, n);
        int L=1, R=(n)/2, k=0;
        while(L<=R)
        {
            int Len=(L+R)/2, flog=0;

            if(dfs(Len))
            {
                L=Len+1, k=Len;
            }
            else
            {
                R=Len-1;
            }
        }
        printf("%d\n", k);
    }

    return 0;
}