微软编程一小时题目2： Longest Repeated Sequence

题目2 : Longest Repeated Sequence

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

You are given a sequence of integers, A = a₁, a₂, ... a_n. A consecutive subsequence of A (say a_i, a_i+1 ... a_j) is called a "repeated sequence" if it appears more than once in A (there exists some positive k that a_i+k = a_i, a_i+k+1 = a_i+1, ... a_j+k = a_j) 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, a₁ a₂ ... a_n (0 <= a_i <= 100).

输出

The length of the longest repeated sequence.

样例输入

5
2 3 2 3 2

样例输出

     2

看到这个题，首先能够想到的思路有很多，KMP，后缀数组等等，然而限于时间限制，我暂时能够想到的方法就是暴搜了（-.-!请见谅）:

首先有个关键问题需要注意一下， 本题是不可重叠最长子串的问题，不能直接套用后缀数组（参看《编程珠玑》p156），也不能直接套用kmp. （在后续博文中，我再给出其他的解法）。
由于是不可重叠最长子串的问题，如果原串的长度为L，那么子串长度Ls理论上能够达到的最大值为 floor(L/2).

本人思路如下：（如有问题，请各位指出，交流交流经验吧）

寻找数组中能够出现的首个最大长度重复子串的过程：

Input L： 数组的长度
Input A:  待查找数组
Output maxlen: 最长重复子串的长度

for k <- L/2 to 2
    for i <- 0 to L - k
        for j <- i+ k to L
            if  comlen(A, i,j,L,k)  // 判断长度为k的重复子串是否存在
                maxLen <- k
                return maxLen
return maxLen

源码如下：

 1 /**********************************************
 2   @author: lsc
 3   @time: 2014-04-05 
 4 ***********************************************/
 5 #include <iostream>
 6 using namespace std;
 7  
 8 /***********************************************
 9  * comlen:
10  *         i:     查找串T的起始位置 
11  *         j:     模式串P的起始位置
12  *         size： 数组边界
13  *         k:     子串长度
14  *  返回值：
15  *       true： 存在长度为k的重复子串
16  *       false： 不存在长度为k的重复子串  
17 ************************************************/
18 bool comlen(int a[], int i, int j,int size,int k)
19 {
20     int len = 0;
21     while(i<size && j<size && a[i++] == a[j++])
22     {
23         ++len;
24         if(len==k)
25           return true;
26     }
27     return false;
28 }
29 
30 /***********************************************
31  * LRS_base: 查找主逻辑
32  *          maxlen: 记录最长重复子串长度
33  *          arr： 带查找串 
34 ***********************************************/
35 int LRS_base(int arr[], int size)
36 {
37     int k,maxlen,i,j;
38     maxlen=1;
39     
40     for(k=size/2;k>=2;k--)
41     {
42        for(i = 0; i < size-k; ++i)
43        {
44           for( j = i+ k; j < size; ++j)
45           {
46             if(comlen(arr,i,j,size,k)==true)
47             {
48                 maxlen = k;
49                 return maxlen;
50             }
51          }
52        }
53     }
54    return maxlen; 
55 }
56 
57 int main()
58 {
59     int a[301]={0},n; 
60     cin>>n;
61     if(n<=0||n>300)
62       exit(0);
63     for(int i=0;i<n;i++) cin>>a[i];
64     cout<<LRS_base(a,n)<<endl;
65 
66     return 0;
67 }

转载请注明出处：http://www.cnblogs.com/double-win/

微软编程一小时 题目2： Longest Repeated Sequence

题目2 : Longest Repeated Sequence

描述

输入

输出

微软编程一小时题目2： Longest Repeated Sequence