描述

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.

 /**********************************************

   @author: lsc

   @time: 2014-04-05

 ***********************************************/

 #include <iostream>

 using namespace std;

 /***********************************************

  * comlen:

  *         i:     查找串T的起始位置

  *         j:     模式串P的起始位置

  *         size： 数组边界

  *         k:     子串长度

  *  返回值：

  *       true： 存在长度为k的重复子串

  *       false： 不存在长度为k的重复子串

 ************************************************/

 bool comlen(int a[], int i, int j,int size,int k)

 {

     int len = ;

     while(i<size && j<size && a[i++] == a[j++])

     {

         ++len;

         if(len==k)

           return true;

     }

     return false;

 }

 /***********************************************

  * LRS_base: 查找主逻辑

  *          maxlen: 记录最长重复子串长度

  *          arr： 带查找串

 ***********************************************/

 int LRS_base(int arr[], int size)

 {

     int k,maxlen,i,j;

     maxlen=;

     for(k=size/;k>=;k--)

     {

        for(i = ; i < size-k; ++i)

        {

           for( j = i+ k; j < size; ++j)

           {

             if(comlen(arr,i,j,size,k)==true)

             {

                 maxlen = k;

                 return maxlen;

             }

          }

        }

     }

    return maxlen;

 }

 int main()

 {

     int a[]={},n;

     cin>>n;

     if(n<=||n>)

       exit();

     for(int i=;i<n;i++) cin>>a[i];

     cout<<LRS_base(a,n)<<endl;

     return ;

 }