大家好,又见面了,我是全栈君。
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.
暴力枚举全部情况
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
char str[205];
int main(){
int n;
while(cin>>str>>n){
int len = strlen(str);
int L = len+n-(len+n)%2; //保证长度为偶数
if(len <= n){
cout<<L<<endl;
continue;
}
int maxlen = 0;
for(int i=0; i<len; i++){ //枚举起始位置
for(int j=1; i+j-1<=len-1; j++){ //枚举一半的长度
int cnt = 0;
for(int k=i; k<=i+j-1; k++){ //推断
if(len <= k+j && k+j < len+n) cnt++; //下标
else if(str[k] == str[k+j]) cnt++;
}
if(cnt == j && 2*cnt > maxlen)
maxlen = 2*cnt;
}
}
cout<<maxlen<<endl;
}
return 0;
}
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/115383.html原文链接:https://javaforall.cn