提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其它

当前栏目

Codeforces 443 B. Kolya and Tandem Repeat

and Codeforces repeat 443
2023-09-14 09:08:06 时间


纯粹练JAVA....

B. Kolya and Tandem Repeat
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Kolya got string s for his birthday, the string consists of small English letters. He immediately added k more characters to the right of the string.

Then Borya came and said that the new string contained a tandem repeat of length l as a substring. How large could l be?

See notes for definition of a tandem repeat.

Input

The first line contains s (1 ≤ |s| ≤ 200). This string contains only small English letters. The second line contains number k (1 ≤ k ≤ 200) — the number of the added characters.

Output

Print a single number — the maximum length of the tandem repeat that could have occurred in the new string.

Sample test(s)
input
aaba
2
output
6
input
aaabbbb
2
output
6
input
abracadabra
10
output
20
Note

A tandem repeat of length 2n is string s, where for any position i (1 ≤ i ≤ n) the following condition fulfills: si = si + n.

In the first sample Kolya could obtain a string aabaab, in the second — aaabbbbbb, in the third — abracadabrabracadabra.





import java.util.*;

public class Main
{
	public static void main(String[] args)
	{
		Scanner cin=new Scanner(System.in);
		String str=cin.next();
		int k=cin.nextInt();
		int ans=2;
		while(k-->0)
		{
			str=str+"*";
			for(int len=ans/2;2*len<=str.length();len++)
			{
				for(int i=0;i+2*len-1<str.length();i++)
				{
					boolean flag=true;
					int u=i,v=i+len;
					for(int j=0;j<len&&flag;j++)
					{
						if(str.charAt(u+j)=='*'||str.charAt(v+j)=='*') continue;
						if(str.charAt(u+j)==str.charAt(v+j)) continue;
						else flag=false;
					}
					if(flag)
						ans=Math.max(ans,len*2);
				}
			}
		}
		System.out.println(ans);
	}
}


版权声明：来自: 代码代码猿猿AC路 http://blog.csdn.net/ck_boss

相关文章