链接
传送门
题意
给出一个字符串，输出它的最长回文子串。
思路
将原字符串反转后求LCS，保留字典序最小的LCS。由求出的LCS字典序最小，因而无法保证回文，比如：\(cbcabcb\)、\(bcbacbc\)求出的LCS为\(bcabc\)，而最长回文子串\(bcacb\)由于字典序比\(bcabc\)大被替换掉了。因此要取LCS前半部分构造出回文子串。
代码
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
43
44
45
46
47
48
49
50
51
| #include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
using namespace std;
const int maxn = 1010;
char s1[maxn], s2[maxn];
struct node {
int len;
string s;
bool operator < (const node& rhs) const {
return len > rhs.len || (len == rhs.len && s < rhs.s);
}
} d[maxn][maxn];
int main() {
while (~scanf("%s", s1 + 1)) {
int len = int(strlen(s1 + 1));
for (int i = 1; i <= len; ++i) {
s2[i] = s1[len - i + 1];
}
s2[len + 1] = 0;
for (int i = 0; i <= len; i++) {
d[0][i].len = 0, d[0][i].s = "";
}
for (int i = 1; i <= len; ++i) {
for (int j = 1; j <= len; ++j) {
if (s1[i] == s2[j]) {
d[i][j].len = d[i - 1][j - 1].len + 1;
d[i][j].s = d[i - 1][j - 1].s + s1[i];
} else {
d[i][j] = min(d[i][j - 1], d[i - 1][j]);
}
}
}
node& k = d[len][len];
len = k.len >> 1;
for (int i = 0; i < len; ++i) {
putchar(k.s[i]);
}
if (k.len & 1) {
putchar(k.s[len]);
}
for (int i = len - 1; i >= 0; --i) {
putchar(k.s[i]);
}
puts("");
}
return 0;
}
|