Musical Theme(后綴數組)

題意：

n個數，選取一段子序列，滿足以下條件：
1.長度至少為5
2.在數列中其他位置出現過(允許轉置)
3.與其他位置出現的不重疊
轉置：將恒定的正或負值添加到子序列上
例如：
n個數為1，2,3，4,5，6,7，8,9，10
12345是一段子序列，那6,7，8,9，10也是，因為前者加5等于后者，且兩者沒有重疊

題解：

人是傻的，完全不會。。。
雖然兩段序列不相等，但是也是有關系的，他們的差分區間相同，也就是其兩兩之間的差值一樣，這樣題目就轉化成不重疊的最長公共子串問題
可以用二分+后綴數組
我們將原數組前后相減得到的新數據做后綴數組
二分的check：
二分最大長度k
檢查兩個子串是否不想交且公共前綴>=k
順序掃描height數組
(height反應的是相鄰兩個后綴的lcp長度)
把height>=k的放在一起統計(將公共前綴>=k滿足條件的串放在一起)，這是為了實現公共前綴>=k

保證其中最大的sa - 最小的sa > k,說明兩個子串的位置距離差大于k，這是為了保證不相交
（SA[i]排序第i的后綴的開始位置）

例如字符串=“aabaaaab’”
當k=2時，后綴分為四組

最長公共前綴不小于k 的兩個后綴一定在同一組

代碼：

#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const int maxm = 100005; const int INF = 1e9 + 7; int a[maxm], b[maxm], sa[maxm], s[maxm], Rank[maxm], id[maxm], Height[maxm]; int n, m; void Rsort() {for (int i = 0; i <= m; i++) s[i] = 0;for (int i = 1; i <= n; i++) s[Rank[id[i]]] ++;for (int i = 1; i <= m; i++) s[i] += s[i - 1];for (int i = n; i >= 1; i--) sa[s[Rank[id[i]]] --] = id[i]; } int cmp(int *f, int x, int y, int w) {return f[x] == f[y] && f[x + w] == f[y + w]; } void suffix() {for (int i = 1; i <= n; i++) Rank[i] = a[i], id[i] = i;m = 200, Rsort();for (int w = 1, p = 1, i; p < n; w += w, m = p){for (p = 0, i = n - w + 1; i <= n; i++) id[++p] = i;for (i = 1; i <= n; i++) if (sa[i] > w) id[++p] = sa[i] - w;Rsort(), swap(Rank, id), Rank[sa[1]] = p = 1;for (i = 2; i <= n; i++) Rank[sa[i]] = cmp(id, sa[i], sa[i - 1], w) ? p : ++p;}int j, k = 0;for (int i = 1; i <= n; Height[Rank[i++]] = k)for (k = k ? k - 1 : k, j = sa[Rank[i] - 1]; a[i + k] == a[j + k]; k++); } int judge(int x) {int mi = INF, mx = -INF;for (int i = 2;i <= n;i++){if (Height[i] >= x){mi = min(mi, min(sa[i], sa[i - 1]));mx = max(mx, max(sa[i], sa[i - 1]));if (mx - mi > x) return 1;}else mi = INF, mx = -INF;}return 0; } int main() {int i, j, k, sum, ans;while (scanf("%d", &n), n != 0){ans = 0;for (i = 1;i <= n;i++) scanf("%d", &b[i]);for (i = 1;i <= n;i++) a[i] = b[i] - b[i - 1] + 100;suffix();int l = 0, r = n * 2;while (r - l > 1){int mid = (r + l) / 2;if (judge(mid)) l = mid, ans = mid;else r = mid;}if (ans >= 4) printf("%d\n", ans + 1);else printf("0\n");}return 0; }

總結

以上是生活随笔為你收集整理的Musical Theme pku1743 (后缀数组)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。