2 seconds
256 megabytes
standard input
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.
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.
Print a single number — the maximum length of the tandem repeat that could have occurred in the new string.
aaba 2
6
aaabbbb 2
6
abracadabra 10
20
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>s.length的情况
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int n,len,k,ans;
int main()
{
string s;
char ch[1001];
cin>>s;
scanf("%d",&k);
len=s.length();
for (int i=len;i>=1;i--)
ch[i]=s[i-1];
for (int s=1;s<=len;s++)
for (int i=1;i<=len-s+1;i++)
{
if (s-1+2*i>len+k) break;
bool mark=0;
for (int j=s+i;j<=min(len,s+i*2-1);j++)
if (ch[j-i]!=ch[j]) {mark=1;break; }
if (!mark) ans=max(i,ans);
}
if (k>len) ans=max(ans,(k+len)>>1);
printf("%d",ans*2);
}