POJ 1743 Musical Theme

NodeKey -

后缀数组求最长不重叠重复子串的入门题。
论文题。
也是男人八题之一。 想我活了十多年终于成了 ( \dfrac {2} {8}) 个男人

虽然说是入门题，但也没有那么简单。
说到底，这道题是我第一次将后缀数组应用起来。我意外的发现，后缀数组之所以强大，在于它拆分了所有后缀，然后又构造了 height 数组描述前缀。这就掌握了所有连续子串。
神了！

这里还是说一下我对最长不重叠重复子串求法的理解。
直接求最长不重叠重复子串是困难的，但对于一个确定的长度 len ，我们却可以( O\left( n \right) ) 地判断其可行性。而这长度又具有单调性，这就使得我们可以用二分的思维去解决它。可行性判断方法如下：

前面说了，sa + height 可以用来描述子串 不是所有。不考虑其它，height 可以单纯的描述为存在的一个公共子串长度。而这个长度大于 len 是我们的必要条件。接下来要判断的就是是否会产生重叠。
sa数组记录的是这个公共子串所对应的后缀起始位置，如果两个后缀它们的起始位置大于等于 len ,毫无疑问，不会重叠。
因此我们只需要在连续的满足 ( height \geq len ) 的 sa 数组中的( \max(sa) – \min(sa) \geq len )，那么存在长度为 len 的不重叠重复子串。
为什么必须是连续的呢，我们大可以在纸上操作一下，只有连续的 height ，它们两两之间都会存在长度相同的子串。

题意：
给你一串数字，要你找出满足要求的两个字段。要求如下 ：

  1. 长度大于等于 ( 5 )
  2. 两个字段相似。其中相似的定义在于两个字段的每个字符，它与前一字符的差值相同

思路：
首先将输入处理一下，单方向让每一个相邻的字符相减，这样问题才近似转变成一个最长不重复子串的问题。

说近似的原因在于，同一个元素可能会被两个字段所共用。比如原字段 1 2 3 —-> 1 1 ,这时候你判定在转化后的序列中存在长度为 ( 1)的 不重叠重复子串的话，显然是错的。
不过处理起来也挺简单的

之后就是关于最长不重叠重复子串的算法了。上面已经有陈述了。

AC Code

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

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

const int inf = 0x3f3f3f3f;
const int maxn = 2e4 + 5;

int sa[maxn];
int t1[maxn], t2[maxn], buc[maxn];
int rnk[maxn], height[maxn];

void buildSA(int s[], int n, int m)
{
    int p, *x = t1, *y = t2;
    each(i, m) buc[i] = 0;
    each(i, n) buc[x[i] = s[i]]++;
    range(i, 1, m - 1) buc[i] += buc[i - 1];
    reach(i, n) sa[--buc[x[i]]] = i;
    for (int k = 1; k <= n; k <<= 1) {
        p = 0;
        range(i, n - k, n - 1) y[p++] = i;
        each(i, n) if (sa[i] >= k) y[p++] = sa[i] - k;
        each(i, m) buc[i] = 0;
        each(i, n) buc[x[i]]++;
        range(i, 1, m - 1) buc[i] += buc[i - 1];
        reach(i, n) sa[--buc[x[y[i]]]] = y[i];
        swap(x, y);
        p = 1, x[sa[0]] = 0;
        range(i, 1, n - 1) x[sa[i]] = y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k] ? p - 1 : p++;
        if (p >= n)
            break;
        m = p;
    }
}

void getHeight(int s[], int n)
{
    int j, k = 0;
    each(i, n + 1) rnk[sa[i]] = i;
    each(i, n)
    {
        k ? k-- : 0;
        j = sa[rnk[i] - 1];
        while (s[i + k] == s[j + k])
            k++;
        height[rnk[i]] = k;
    }
}

bool judge(int len, int n)
{
    int mx = -inf, mm = inf;
    for (int i = 2; i <= n; ++i) {
        if (height[i] >= len) {
            mm = min(mm, min(sa[i], sa[i - 1]));
            mx = max(mx, max(sa[i], sa[i - 1]));
            if (mx - mm > len)
                return true;
        } else
            mx = -inf, mm = inf;
    }
    return false;
}

int s[maxn];

int main()
{
    int n;
    while (scanf("%d", &n) != EOF && n) {
        each(i, n) scanf("%d", s + i);
        each(i, n - 1) s[i] = s[i + 1] - s[i] + 88;
        s[--n] = 0;
        buildSA(s, n + 1, 88 * 2);
        getHeight(s, n);
        int l = 0, r = n >> 1, mid;
        while (l <= r) {
            mid = (l + r) >> 1;
            if (judge(mid, n))
                l = mid + 1;
            else
                r = mid - 1;
        }
        printf("%d\n", l > 4 ? l : 0);
    }
    return 0;
}