443B.md (1303B)
1 Source: https://codeforces.com/problemset/problem/443/B 2 3 B. Kolya and Tandem Repeat 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 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. 22 23 Then Borya came and said that the new string contained a tandem repeat of length *l* as a substring. How large could *l* be? 24 25 See notes for definition of a tandem repeat. 26 27 Input 28 29 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. 30 31 Output 32 33 Print a single number — the maximum length of the tandem repeat that could have occurred in the new string. 34 35 Examples 36 37 Input 38 39 ``` 40 aaba 41 2 42 ``` 43 44 Output 45 46 ``` 47 6 48 ``` 49 50 Input 51 52 ``` 53 aaabbbb 54 2 55 ``` 56 57 Output 58 59 ``` 60 6 61 ``` 62 63 Input 64 65 ``` 66 abracadabra 67 10 68 ``` 69 70 Output 71 72 ``` 73 20 74 ``` 75 76 Note 77 78 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*. 79 80 In the first sample Kolya could obtain a string aabaab, in the second — aaabbbbbb, in the third — abracadabrabracadabra.