同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

21776_LongestRepeatedsubsequence

2022-5-16 18:20| 发布者: Hocassian| 查看: 28| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-4-89505835725200-Problem List-采集的数据-后羿采集器.html

Pro.ID

21776

Title

Longest Repeated subsequence

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=21776

AC

Submit

Ratio

36.36%

时间&空间限制

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

描述

Write a program that takes a sequence of number and returns length of the longest repeated subsequence. A repeated subsequence which repeats identically at least K times without overlaps.

For example 1 2 3 1 2 3 2 3 1 repeats 2 3 for three times.

输入

Line 1: The input contains a single integer T , the number of test cases.

Line 2: Two space-separated integers: N and K (1 ≤ N ≤ 50000), (2 ≤ K ≤ N)

Lines 3..N+2: N integers, one per line. The integer is between 0 and 10⁹.

It is guaranteed that at least one subsequence is repeated at least K times.

输出

Description

Write a program that takes a sequence of number and returns length of the longest repeated subsequence. A repeated subsequence which repeats identically at least K times without overlaps.

For example 1 2 3 1 2 3 2 3 1 repeats 2 3 for three times.

Input

Line 1: The input contains a single integer T , the number of test cases.

Line 2: Two space-separated integers: N and K (1 ≤ N ≤ 50000), (2 ≤ K ≤ N)

Lines 3..N+2: N integers, one per line. The integer is between 0 and 10⁹.

It is guaranteed that at least one subsequence is repeated at least K times.

Output

For each test case, the first line print the length n of the Longest Repeated Subsequence and the line 2…n+1 print the subsequence numbers.

if we have several subsequence with the same length output the lexicographic order smallest one). Separate output for adjacent cases with a single blank line.

Sample Input

1
8 2
1
2
3
2
3
2
3
1

Sample Output

2
2
3

Source

2009 Multi-University Training 9