本文主要是介绍CodeForces 443B Kolya and Tandem Repeat，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
链接：http://codeforces.com/problemset/problem/443/B
Kolya and Tandem Repeat
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)
aaba 2
6
aaabbbb 2
6
abracadabra 10
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个任意的字符。问你这个新串中包含的重复序列的最大长度为多大。重复序列是这样定义的：一个长度为2n的重复序列s满足si=si+n，1<=i<=n。
思路——因为字符长度最大为200，k最大也只为200，所以直接暴力枚举即可解决。首先可以特判一下字符串长度和k的关系，如果字符串长度小于等于k，那么直接输出该长度加上k除以二取整再乘以二即可。否则，从串首开始枚举。枚举的是重复序列一半的长度，当该长度满足重复序列的条件时，将它与当前最长长度比较，大的话，就将最大值改为现在的长度，否则不变。最后枚举完所有字符，输出那个最大值乘以二即可。
复杂度分析——时间复杂度:O(len^2),空间复杂度:O(len)
附上AC代码：
#include <iostream>
#include <cstdio>
#include <string>
#include <cmath>
#include <iomanip>
#include <ctime>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <set>
#include <map>
//#pragma comment(linker, "/STACK:102400000, 102400000")
using namespace std;
typedef unsigned int li;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const double pi = acos(-1.0);
const double e = exp(1.0);
const double eps = 1e-8;
const short maxlen = 205;
char str[maxlen];
short k;int main()
{ios::sync_with_stdio(false);while (~scanf("%s%hd", str, &k)){short len = strlen(str);if (len <= k){printf("%d\n", (len+k)/2*2);continue;}short maxnum = 0;for (short i=0; i<len; i++){for (short j=1; j<=len-i; j++){short cnt = 0;for (short s=i; s<i+j; s++){if (s+j>=len && s+j<len+k)cnt++;else if (s+j<len && str[s]==str[s+j])cnt++;}if (j == cnt)maxnum = max(maxnum, cnt);}}printf("%d\n", maxnum*2);}return 0;
}
这篇关于CodeForces 443B Kolya and Tandem Repeat的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
