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 2_n_ is string s, where for any position i (1 ≤ i ≤ n) the following condition fulfills: s__i = s__i + n.
In the first sample Kolya could obtain a string aabaab, in the second – aaabbbbbb, in the third – abracadabrabracadabra.
大力出奇迹2333
代码实现
1
2 /*************************************************************************
3 > File Name: code/2015summer/#3/A.cpp
4 > Author: 111qqz
5 > Email: rkz2013@126.com
6 > Created Time: 2015年07月28日 星期二 12时27分08秒
7 ************************************************************************/
8
9 #include<iostream>
10 #include<iomanip>
11 #include<cstdio>
12 #include<algorithm>
13 #include<cmath>
14 #include<cstring>
15 #include<string>
16 #include<map>
17 #include<set>
18 #include<queue>
19 #include<vector>
20 #include<stack>
21 #define y0 abc111qqz
22 #define y1 hust111qqz
23 #define yn hez111qqz
24 #define j1 cute111qqz
25 #define tm crazy111qqz
26 #define lr dying111qqz
27 using namespace std;
28 #define REP(i, n) for (int i=0;i<int(n);++i)
29 typedef long long LL;
30 typedef unsigned long long ULL;
31 const int N=1E4+5;
32 char a[N];
33 int k;
34 int main()
35 {
36
37 cin>>a>>k;
38 int l=strlen(a);
39 int m,ans;
40 m=l+k;
41 if (m%2==1) m--;
42 if(k>=l)
43 {
44 cout<<m<<endl;
45 return 0;
46 }
47 int max=0;
48 for(int i = 0 ; i < l ; i++)
49 {
50 for(int j = 1 ; j <= l-i;j++)
51 {
52 ans = 0;
53 for(int o = i ; o < i+j ; o++)
54 {
55
56 if(o+j>=l&&o+j<l+k)
57 ans++;
58 else if(a[o]==a[o+j])
59 ans++;
60 }
61 if(ans==j&&2*ans>max)
62 max=2*ans;
63 }
64 }
65 cout<<max<<endl;
66 return 0;
67 }