POJ 1743 Musical Theme 【后缀数组最长不重叠子串】

Musical Theme

Time Limit: 1000MS		Memory Limit: 30000K
Total Submissions: 36590		Accepted: 12087

Description

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

Hint

Use scanf instead of cin to reduce the read time.

Source

LouTiancheng@POJ

题意概括：

给一个长度为 N 的序列，要求找长度不少于 5 的两个不重叠“相似”子串。

（本弱鸡一开始直接以为是找不重叠相同子串，样例都没过）。

相似的定义是长度相等且每一位的数字差都相等。

解题思路：

当然是传统经典口味：后缀数组啦（好吧，就是板子题）

首先处理出 sa 和 height（废话）（怎么处理？@模板）

当然主串就不是输入那个了，而是相邻两个的值两两作差，得到一个新的主串，

在这个主串里找到两个不重叠相同子串，那么原序列里就对应两个相似主串了（为什么？因为题目要求的相似就是数字差相等嘛）

（不过要注意一点就是在新主串找的两个子串不能紧接在一起，因为这个串是数字差的结果，在原串中就会变成首尾相接了。）

二分可满足的长度 len，判断是否有满足条件的两个不重叠子串。

判断过程：先按 height 分组，然后比较组内的最大的sa 和最小的sa 差值是否满足 len。

AC code：

  1 //#include<bits/stdc++.h>
  2 #include <set>
  3 #include <map>
  4 #include <string>
  5 #include <cstdio>
  6 #include <vector>
  7 #include <iostream>
  8 #include <algorithm>
  9 #define mem(i, j) memset(i, j, sizeof(i))
 10 #define inc(i, j, k) for(int i = j; i <= k; i++)
 11 #define rep(i, j, k) for(int i = j; i < k; i++)
 12 #define gcd(i, j) __gcd(i, j)
 13 #define INF 0x3f3f3f3f
 14 #define LL long long
 15 using namespace std;
 16 const int MAXN = 2e5+10;
 17 int r[MAXN];
 18 int wa[MAXN], wb[MAXN], wv[MAXN], tmp[MAXN];
 19 int sa[MAXN];
 20 
 21 int cmp(int *r, int a, int b, int l)
 22 {
 23     return r[a] == r[b] && r[a + l] == r[b + l];
 24 }
 25 void da(int *r, int *sa, int n, int m)
 26 {
 27     int i, j, p, *x = wa, *y = wb, *ws = tmp;
 28     for (i = 0; i < m; i++) ws[i] = 0;
 29     for (i = 0; i < n; i++) ws[x[i] = r[i]]++;
 30     for (i = 1; i < m; i++) ws[i] += ws[i - 1];
 31     for (i = n - 1; i >= 0; i--) sa[--ws[x[i]]] = i;
 32     for (j = 1, p = 1; p < n; j *= 2, m = p)
 33     {
 34         for (p = 0, i = n - j; i < n; i++) y[p++] = i;
 35         for (i = 0; i < n; i++)
 36             if (sa[i] >= j) y[p++] = sa[i] - j;
 37         for (i = 0; i < n; i++) wv[i] = x[y[i]];
 38         for (i = 0; i < m; i++) ws[i] = 0;
 39         for (i = 0; i < n; i++) ws[wv[i]]++;
 40         for (i = 1; i < m; i++) ws[i] += ws[i - 1];
 41         for (i = n - 1; i >= 0; i--) sa[--ws[wv[i]]] = y[i];
 42         for (swap(x, y), p = 1, x[sa[0]] = 0, i = 1; i < n; i++)
 43             x[sa[i]] = cmp(y, sa[i - 1], sa[i], j) ? p - 1 : p++;
 44     }
 45 }
 46 int Rank[MAXN]; //index range 0~n-1 value range 1~n
 47 int height[MAXN]; //index from 1   (height[1] = 0)
 48 void calheight(int *r, int *sa, int n)
 49 {
 50     int i, j, k = 0;
 51     for (i = 1; i <= n; ++i) Rank[sa[i]] = i;
 52     for (i = 0; i < n; height[Rank[i++]] = k)
 53         for (k ? k-- : 0, j = sa[Rank[i] - 1]; r[i + k] == r[j + k]; ++k);
 54     return;
 55 }
 56 int N, num[MAXN];
 57 bool check(int len, int n)
 58 {
 59     int flag = false;
 60     int mnn = n, mxx = -1;
 61     for(int i = 2; i <= N; i++){
 62 
 63         if((i == N && flag) || (height[i] < len && flag)){
 64             flag = false;
 65             mnn = min(mnn, sa[i-1]);
 66             mxx = max(mxx, sa[i-1]);
 67             if(mxx-mnn >= len){
 68                 return true;
 69             }
 70             mnn = n;
 71             mxx = -1;
 72         }
 73         else if(height[i] >= len){
 74             flag = true;
 75             mnn = min(mnn, sa[i-1]);
 76             mxx = max(mxx, sa[i-1]);
 77         }
 78     }
 79     return false;
 80 }
 81 
 82 int main()
 83 {
 84     while(~scanf("%d", &N) && N != 0){
 85         inc(i, 0, (N-1)) scanf("%d", &num[i]);
 86         rep(i, 0, (N-1)) r[i] = num[i+1]-num[i]+89;
 87         r[N-1] = 0;
 88         da(r, sa, N, 200);
 89         calheight(r, sa, (N-1));
 90 //        puts("zjj");
 91         int ans = 0;
 92         int L = 4, R = N/2, mid;
 93         while(L <= R)
 94         {
 95             mid = (L+R)>>1;
 96             if(check(mid, N)){
 97                 L = mid+1;
 98                 ans = max(ans, mid);
 99             }
100             else R = mid-1;
101         }
102         if(ans < 4) puts("0");
103         else printf("%d
", ans+1);
104     }
105     return 0;
106 }

View Code

POJ 1743 Musical Theme 【后缀数组 最长不重叠子串】

Musical Theme

POJ 1743 Musical Theme 【后缀数组最长不重叠子串】