最长子串
题目描述
给出一个全部由小写字母构成的字符串，要求从该串中找出满足下面条件的最长子串：
条件1：子串是连续的；
条件2：子串的长度是偶数；
条件3：沿子串的中心切开，对左右两部分的串按顺序进行比较，要求不同的字符对数 $N$ 不超过题目给出的一个限定值 $D$。
比如：abcaec 的 $N$ 值为 $1$。因为平分的两部分 abc 和 aec 比较，只有 $1$ 对字符不同：即 b 和 e，而其余字符都相同。
输入格式
只有一行，先是一个整数 $D(0 \leq D \leq 1000)$，然后一个空格，接着是一个由小写字母构成的字符串（长度不超过 $2000$）。
输出格式
如果找到满足条件的最长子串，则按如下格式输出一行：
先是一个整数X，表示最长子串的长度，然后一个空格，接着是满足条件的最长子串。
如果有多解，则输出左端点在原串中最靠前的子串，如果找不到满足条件的最长子串，则输出 Not found
样例数据 1
输入
输出
样例数据 2
输入
输出
样例数据 3
输入
输出
方法一
直接暴力
三重循环直接比较即可(评测机速度比较快就不会超时),时间复杂度 $O(n ^ 3)$。
源码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| #include <iostream>
#include <string>
using namespace std;
int d;
string str;
int val_length = 0;
int val_pos = -1;
int dif;
int main() {
cin >> d >> str;
for (int i = 0, range = str.length(); i < range; i++) {
for (int j = i + 1; j < range; j += 2) {
int mid_pos = (j + i) >> 1;
dif = 0;
for (int m = i, n = mid_pos + 1; m <= mid_pos; m++, n++)
if (str[m] != str[n]) dif++;
int len = j - i + 1;
if (dif <= d && len > val_length) val_length = len, val_pos = i;
}
}
if (val_pos != -1)
cout << val_length << " " << str.substr(val_pos, val_length);
else
cout << "Not found"
<< "\n";
return 0;
}
|
方法二
正解
从中间开始查找,谨慎使用 string,(方法一把 string 换成 char 就快多了)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| #include <cstring>
#include <iostream>
#include <string>
using namespace std;
char t[2005], s[2005];
int f[2005], a[2005];
int d, h, hh;
int m, u;
bool b = false;
int main() {
cin >> d >> s;
h = strlen(s);
hh = h >> 1;
for (int i = hh; i > 0; i--) {
for (int j = i; j < h; j++)
if (s[j] != s[j - i])
f[j] = 1;
else
f[j] = 0;
a[i] = f[i];
m = i << 1;
for (int j = i + 1; j < m; j++) a[j] = a[j - 1] + f[j];
for (int j = m; j < h; j++) a[j] = a[j - 1] + f[j] - f[j - i];
for (int j = m - 1; j < h; j++)
if (a[j] <= d) {
b = true;
u = 0;
for (int k = j - m + 1; k <= j; k++) t[u++] = s[k];
t[m] = 0;
cout << m << " " << t;
break;
}
if (b) break;
}
if (!b)
cout << "Not found"
<< "\n";
return 0;
}
|
