[Codeforces443B]Kolya and Tandem Repeat

2014-06-20
竞赛题解 / 模拟
Codeforces

描述 Description

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.

输入格式 InputFormat

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.

输出格式 OutputFormat

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

样例输入 SampleInput

abracadabra

10

​
## 样例输出 SampleOutput >20

Codeforces 443B

代码 Code

a tandem repeat 的意思是所求的重复子串当且仅当重复了两次 =_=

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
char s[500];
int i,j,t,n,m,l,r,k,z,y,x,ans;
inline bool equal(char a,char b)
{
    if (a==s[0] || b==s[0] || a==b) return true;
    else return false;
}
int main()
{
    scanf("%s",s+1);scanf("%d",&k);
    s[0]='#';m=strlen(s)-1;
    for (i=m+1;i<=m+k;i++) s[i]=s[0];
    m+=k;
    ans=k;
    for (l=1;l<m;l++)
    {
        for (n=1;n<=m;n++)
        {
            if (2*n+l-1>m) break;
            for (i=1;i<=n;i++) if (!equal(s[l+i-1],s[l+n+i-1])) break;
            if (i>n) ans=max(ans,n*2);
        }
    }
    printf("%d\n",ans);
    return 0;
}