题目分析

题目要求在一个音符序列中找出最长的"主题"，该主题需要满足：

1. 长度至少为5个音符
2. 在序列的其他位置以转调形式重复出现（所有音符加减相同值）
3. 重复出现的位置与原位置不重叠

解题思路

1. 差分转换：将原序列转换为差分序列，使转调问题转化为寻找相同子序列问题
2. 后缀数组：构建差分序列的后缀数组，用于高效查找重复子串
3. 高度数组：通过高度数组快速检查重复子串
4. 二分答案：使用二分法确定可能的最大主题长度
5. 验证函数：检查是否存在满足条件的重复子串

标准程序代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 20005
using namespace std;

int n, m, x[N], y[N], S[N], height[N], Rank[N], sa[N], sum[N];

void build_suffix_array() {
    int i, j, p;
    memset(sum, 0, sizeof(sum));
    for (i = 1; i <= n; ++i) sum[x[i] = S[i]]++;
    for (i = 2; i <= m; ++i) sum[i] += sum[i - 1];
    for (i = n; i >= 1; --i) sa[sum[x[i]]--] = i;
    
    for (j = 1; j <= n; j <<= 1) {
        p = 0;
        for (i = n - j + 1; i <= n; ++i) y[++p] = i;
        for (i = 1; i <= n; ++i) if (sa[i] > j) y[++p] = sa[i] - j;
        
        memset(sum, 0, sizeof(sum));
        for (i = 1; i <= n; ++i) sum[x[y[i]]]++;
        for (i = 2; i <= m; ++i) sum[i] += sum[i - 1];
        for (i = n; i >= 1; --i) sa[sum[x[y[i]]]--] = y[i];
        
        swap(x, y);
        p = 1, x[sa[1]] = 1;
        for (i = 2; i <= n; ++i)
            x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + j] == y[sa[i - 1] + j]) ? p : ++p;
        if (p == n) break;
        m = p;
    }
}

void build_height_array() {
    int i, k = 0;
    for (i = 1; i <= n; ++i) Rank[sa[i]] = i;
    for (i = 1; i <= n; ++i) {
        if (Rank[i] == 1) continue;
        if (k) k--;
        int j = sa[Rank[i] - 1];
        while (i + k <= n && j + k <= n && S[i + k] == S[j + k]) k++;
        height[Rank[i]] = k;
    }
}

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

int main() {
    while (scanf("%d", &n), 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--;
        m = 200;
        build_suffix_array();
        build_height_array();
        
        int low = 4, high = n, ans = 0;
        while (low <= high) {
            int mid = (low + high) >> 1;
            if (check(mid)) {
                ans = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        printf("%d\n", ans >= 4 ? ans + 1 : 0);
    }
    return 0;
}

代码说明

1. 后缀数组构建：使用基数排序和倍增算法高效构建后缀数组
2. 高度数组计算：通过相邻后缀的最长公共前缀构建高度数组
3. 二分验证：检查是否存在满足条件的重复子串
4. 差分处理：将原序列转换为差分序列处理转调问题
5. 边界处理：确保主题长度至少为5且不重叠