2014微軟程式設計一小時題目2 : Longest Repeated Sequence

題目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      

找到最長的重複序列長度：因為i+K>j  序列為a1,a2，……ai，ai+1，ai+2，……，aj，……，ai+k，ai+1+k, ai+2+k,……aj+k,……an    其中ai+k = ai, ai+k+1 = ai+1, ... aj+k = aj，重複序列長度為j，重複序列為ai，ai+1，ai+2，……aj      

#include <iostream>
#include <vector>
using namespace std;

int main()
{
	int n;
	vector<int> v;
	int ival;
	int longestlength = 0;//記錄The length of the longest repeated sequence.

	//input n
	cin >> n;

	//intput vector
	while(n-- > 0 && cin >> ival)
	{
		v.push_back(ival);
	}


	//The length of the longest repeated sequence.
	for(vector<int>::size_type i = 0 ; i != v.size() - 1 ; ++i )//i序列開始位置
	{
		for(vector<int>::size_type k = 1 ; i + k < v.size() ; ++k )//k步長
		{
			int j = i;//序列最後一個元素位置
			int ii = i;//ii = i，i+1,i+2 ... j

			while(i + k > j && ii + k < v.size() && v[ii] == v[ii + k])//判斷序列長度
			{
				ii++;
				j++;
			}

			j--;//最後一個不滿足條件，回退

			if((j  - i + 1) > longestlength) //本次重複序列長度 = j-i+1
			{
				longestlength = j - i + 1;
			}
		}
	}

	cout << longestlength << endl;

	return 0;
}