# 求最长不重叠子串

2018/05/16 23:21

A musical melody is represented as a sequence of N (1<=N<=20000)notes that are integers in the range 1..88, each representing a key on the piano. It is unfortunate but true that this representation of melodies ignores the notion of musical timing; but, this programming task is about notes and not timings.
Many composers structure their music around a repeating &qout;theme&qout;, which, being a subsequence of an entire melody, is a sequence of integers in our representation. A subsequence of a melody is a theme if it:
• is at least five notes long
• appears (potentially transposed -- see below) again somewhere else in the piece of music
• is disjoint from (i.e., non-overlapping with) at least one of its other appearance(s)

Transposed means that a constant positive or negative value is added to every note value in the theme subsequence.
Given a melody, compute the length (number of notes) of the longest theme.
One second time limit for this problem's solutions!
Input
The input contains several test cases. The first line of each test case contains the integer N. The following n integers represent the sequence of notes.
The last test case is followed by one zero.
Output
For each test case, the output file should contain a single line with a single integer that represents the length of the longest theme. If there are no themes, output 0.
Sample Input
``````30
25 27 30 34 39 45 52 60 69 79 69 60 52 45 39 34 30 26 22 18
82 78 74 70 66 67 64 60 65 80
0``````
Sample Output
``5``
Hint

1，长度至少为5

2，序列可以转调，即存在两个子序列，满足一个子序列加/减一个数后可以得到另一个序列

3，两个序列不能有相交的部分。

``````/*

1，长度至少为5
2，序列可以转调，即存在两个子序列，满足一个子序列加/减一个数后可以得到另一个序列
3，两个序列不能有相交的部分。

*/

#define ll long long
const int maxn = 2e4+5;

/*
-待排序数组长度为 n，放在 0~n-1,在最后加一个'\$',让其比所有的字符串中的字符都小，

*build_sa( ,n+1, );//注意是n+1;
*getheight(,n);
*例如：
*n   = 8;
*num[]   = { 1, 1, 2, 1, 1, 1, 1, 2, \$ };注意num最后一位为0，其他大于0
*rank[]  = { 4, 6, 8, 1, 2, 3, 5, 7, 0 };rank[0~n-1]为有效值，rank[n]必定为0无效值
*sa[]    = { 8, 3, 4, 5, 0, 6, 1, 7, 2 };sa[1~n]为有效值，sa[0]必定为n是无效值
*height[]= { 0, 0, 3, 2, 3, 1, 2, 0, 1 };height[2~n]为有效值
*/

int n;
int a[maxn], s[maxn];
int sa[maxn], rank[maxn], height[maxn];
int t1[maxn], t2[maxn], c[maxn];

bool cmp(int *r, int a, int b, int l){
return r[a] == r[b] && r[a+l] == r[b+l]; // !!!
}

void build_sa(int n, int m){ //m代表估计数字，是ASCll的最大值
int *x = t1, *y = t2;

for(int i = 0; i < m; i++) c[i] = 0;
for(int i = 0; i < n; i++) c[x[i]=s[i]]++;
for(int i = 1; i < m; i++) c[i] += c[i-1];
for(int i = n-1; i >= 0; i--) sa[--c[x[i]]] = i;

for(int j = 1; j <= n; j <<= 1){  // !!!
int p = 0;
for(int i = n-j; i < n; i++) y[p++] = i;
for(int i = 0; i < n; i++) if (sa[i] >= j) y[p++] = sa[i]-j;

for(int i = 0; i < m; i++) c[i] = 0;
for(int i = 0; i < n; i++) c[x[y[i]]]++;
for(int i = 1; i < m; i++) c[i] += c[i-1];
for(int i = n-1; i >= 0; i--) sa[--c[x[y[i]]]] = y[i];

swap(x, y);
p = 1; x[sa[0]] = 0;  // !!!!

for(int i = 1; i < n; i++)
x[sa[i]] = cmp(y, sa[i-1], sa[i], j)?p-1:p++;

if (p >= n) break;
m = p; // 下次基数排序的最大值  !!!
}
}

void getheight(){
int k = 0;
for(int i = 0; i <= n; i++) rank[sa[i]] = i;
for(int i = 0; i < n; i++){
if (k) k--;
int j = sa[rank[i]-1];
while(s[i+k] == s[j+k]) k++;
height[rank[i]] = k;
}
}

bool check(int k){
int Max = sa[1], Min = sa[1];

for(int i = 2; i <= n; i++){
if (height[i] < k) Max = Min = sa[i];
else {
if (sa[i] < Min) Min = sa[i];
if (sa[i] > Max) Max = sa[i];
if (Max - Min >= k) return  true;
}
}
return false;
}

int main() {
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);

while(~scanf("%d", &n) && n){
for(int i = 0; i < n; i++){
scanf("%d", &a[i]);
}
for(int i = 1; i < n; i++){
s[i-1] = a[i]-a[i-1]+90;
}
n--; // 减少一个单位长度
s[n] = 0;
build_sa(n+1, 200); //此时的n是要算上最末尾的特殊字符
getheight(); //此时的n是不算特殊字符的长度

int l = 1, r = n;
int ans = -1;
while(l <= r){
int mid = (l+r)>>1;
if (check(mid)){
ans = mid;
l = mid+1;
}
else r = mid-1;
}
if (ans < 4) printf("0\n");
else printf("%d\n", ans+1); // 这里再加 1 是因为，此串是转换成相邻两差的形式
// 因此要还原最原始的串，则需要长度 +1
}
return 0;
}``````

0
0 收藏

0 评论
0 收藏
0