Codeforces Round #253 (Div. 2) —— B

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.
 
제목 대의: 원 문자열의 끝에 k개의 문자를 추가하여 원 문자열을 두 개의 중복 문자열을 포함하는 문자열로 만들고 이 두 개의 중복 문자열의 총 길이를 구한다.
 
이 문제는 개인적으로 좀 어려워서 오랫동안 해 보고서야 풀었다.나는 좀 어지럽게 썼는데, 주로 모든 상황을 일일이 열거하는 것이다.(사실 이 문제는 테스트 데이터 한 세트를 봤어요=)

#include<stdio.h>
#include<string.h>

int sum(char* m, int len, int k)
{
    int n, i, j, maxn = 0;
    for(n=(len+k)/2; n>=1; n--)
    {
        for(i=1; i+n<=len+k; i++)
        {
            int num = 0, x = 0;
            for(j=i; j+n<=len+k; j++)
            {
                if(m[j] == m[j+n]) num++;
                else  break;
            }
            //if(j+n == len+k+1 && j == i+n) x = num;
            if(j == i+n) x = num;
            if(x > maxn) maxn = x;
        }
    }
    return maxn;
}

int main()
{
    int k, i, j;
    char m[1000];

    while(~scanf("%s", m+1))
    {
        scanf("%d", &k);
        int len = strlen(m+1);
        int num, maxn = 0;
        if(k > len)
        {
            if((len+k)%2) printf("%d
", len+k-1);
            else printf("%d
", len+k);
            continue;
        }
        for(j=1; j<=len-k+1; j++)
        {
            int x = j;
            for(i=1; i<=k; i++)
            {
                m[i+len] = m[x++];
            }
            num = sum(m, len, k);
            if(num > maxn) maxn = num;
        }
        printf("%d
", 2*maxn);
    }
    return 0;
}