cf 443B Kolya and Tandem Repeat

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<br></br>2

output

6

input

aaabbbb<br></br>2

output

6

input

abracadabra<br></br>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   }
68   
69
70
71