好，今晚兴致正浓，再来一篇，再说一遍，只是个人感想，高手一定轻喷啊，小弟还没上路呢。。。
这篇是微软编程一小时的第二题，废话不多说，上题目描述先。
题目2 : Longest Repeated
Sequence
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
You are given a sequence of integers, A = a1, a2,
... an. A consecutive subsequence of A (say ai, ai+1 ... aj) is called a
"repeated sequence" if it appears more than once in A (there exists some
positive k that ai+k = ai, ai+k+1 = ai+1, ... aj+k = aj) and its appearances are
not intersected (i + k > j).
Can you find the longest repeated sequence in A?
输入
Line 1: n (1 <= n <= 300), the length of
A.
Line 2: the sequence, a1 a2 ... an (0 <= ai <= 100).
输出
The length of the longest repeated sequence.
样例输入
5
2 3 2 3 2
样例输出
2
不知道这题有没有哪位大侠直接暴力过的，感觉n的级别，三次方的话1s有点悬。。。我的想法是，用二分法确定序列最长的长度。然后为了快速判断某一个长度是否成立，建立一个next数组，保存的是从右边开始跟它相等的最近的一个元素的位置，若右方没有与之相等的元素，next数组值为-1，这样在寻找序列起始位置的时候就可以根据next数组直接往下跳了，节省了很多不必要的判断时间。不过这题我当时做的时候考虑不周，在使用next数组往后跳的时候只选择了第一个满足条件的位置，忘了后面还可能有很多个满足条件的位置，只得了90分，结果是WA。当时只剩下十几分钟，就没来得及细想，后来同学问我是怎么做的时候，我才发现这个问题，可惜已经无法提交了。先把比赛时候的代码贴出来吧。
1 // 得分: 90 / 100 2 // 题目: Longest Repeated Sequence 3 // 结果: WA 4 // 语言: G++ 5 // 时间: 14ms 6 // 内存: 7MB 7 8 #include <cstdio> 9 #include <cstring> 10 11 const int N = 305; 12 13 int n; 14 int seq[N], next[N]; 15 16 // 判断当前长度是否满足条件 17 bool check(int num) 18 { 19 if (0 == num) 20 return true; 21 int i, j, k, res, up = n - (num << 1) + 1; 22 for (i = 1; i <= up; i++) { 23 // next数组为-1，后面没有相等元素，跳过 24 if (-1 == next[i]) 25 continue; 26 j = next[i]; 27 k = j - i; 28 // 序列长度至少为num，才开始比较 29 while (k < num && -1 != next[j]) { 30 k += next[j] - j; 31 j = next[j]; 32 } 33 if (k < num) 34 continue; 35 // 这个地方只考虑第一个满足条件的j，错了 36 k = i, res = 0; 37 while (seq[k] == seq[j] && j <= n) { 38 res++; 39 k++, j++; 40 if (res >= num) 41 return true; 42 } 43 } 44 return false; 45 } 46 47 int main(void) 48 { 49 int i, j; 50 int left, right, mid; 51 while (EOF != scanf("%d", &n)) { 52 memset(next, -1, sizeof(next)); 53 for (i = 1; i <= n; i++) { 54 scanf("%d", &seq[i]); 55 // 设置元素的next数组，右边与其最接近的相等元素的位置 56 for (j = i - 1; j >= 1; j--) { 57 if (seq[j] == seq[i]) { 58 next[j] = i; 59 break; 60 } 61 } 62 } 63 left = 0, right = (n >> 1) + 1; 64 // 二分法确定满足条件的最长长度 65 while (left <= right) { 66 mid = (left + right) >> 1; 67 if (check(mid)) 68 left = mid + 1; 69 else 70 right = mid - 1; 71 } 72 printf("%d\n", left - 1); 73 } 74 return 0; 75 }
然后这是后来修改的版本，考虑了所有满足条件的位置。
1 #include <cstdio> 2 #include <cstring> 3 4 const int N = 305; 5 6 int n; 7 int seq[N], next[N]; 8 9 // 判断当前长度是否满足条件 10 bool check(int num) 11 { 12 if (0 == num) 13 return true; 14 int i, j, k, res, up = n - (num << 1) + 1; 15 for (i = 1; i <= up; i++) { 16 // next数组为-1，后面没有相等元素，跳过 17 if (-1 == next[i]) 18 continue; 19 j = next[i]; 20 k = j - i; 21 // 序列长度至少为num，才开始比较 22 while (k < num && -1 != next[j]) { 23 k += next[j] - j; 24 j = next[j]; 25 } 26 if (k < num) 27 continue; 28 // 考虑所有满足条件的位置j 29 do { 30 int l = i, r = j; 31 res = 0; 32 while (seq[l] == seq[r] && r <= n) { 33 res++; 34 l++, r++; 35 if (res >= num) 36 return true; 37 } 38 j = next[j]; 39 } while (-1 != j); 40 } 41 return false; 42 } 43 44 int main(void) 45 { 46 int i, j; 47 int left, right, mid; 48 while (EOF != scanf("%d", &n)) { 49 memset(next, -1, sizeof(next)); 50 for (i = 1; i <= n; i++) { 51 scanf("%d", &seq[i]); 52 // 设置元素的next数组，右边与其最接近的相等元素的位置 53 for (j = i - 1; j >= 1; j--) { 54 if (seq[j] == seq[i]) { 55 next[j] = i; 56 break; 57 } 58 } 59 } 60 left = 0, right = (n >> 1) + 1; 61 // 二分法确定满足条件的最长长度 62 while (left <= right) { 63 mid = (left + right) >> 1; 64 if (check(mid)) 65 left = mid + 1; 66 else 67 right = mid - 1; 68 } 69 printf("%d\n", left - 1); 70 } 71 return 0; 72 }
微软编程一小时——Longest Repeated Sequence,布布扣,bubuko.com
微软编程一小时——Longest Repeated Sequence
原文：http://www.cnblogs.com/guikeyi/p/3687418.html