[PAT解题报告] Longest Symmetric String
最长回文子串。
长度不大，1000，可以采用暴力方法解决。时间复杂度O(n2)——即选取中心位置——可能是一个字符，也可能是两个字符之间，看向左和右能延伸的最大长度。相当于枚举所有长度位奇数和偶数的回文串。
还有注意字符串有空白，如果用C输入的话要用gets，不能用scanf。
代码：
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
char s[1024];
int main() {
gets(s);
int n = strlen(s);
int answer = 0;
for (int i = 0; i < n; ++i) {
int len = 0;
for (len = 1; (i - len >= 0) && (i + len < n) && (s[i - len] == s[i + len]); ++len)
;
answer = max(((len - 1) << 1) | 1, answer);
for (len = 0; (i - len >= 0) && (i + len + 1 < n) && (s[i - len] == s[i + len + 1]); ++len)
;
answer = max(len << 1, answer);
}
printf("%d\n",answer);
return 0;
}
另外一个线性的算法叫做Manacher，写起来也不难，有兴趣的读者可以查阅Manacher算法相关的资料。
代码：
#include <string>
#include <cstring>
#include <vector>
#include <cstdio>
using namespace std;
char S[1024];
int run(char *S, int n) {
string s = "#";
for (int i = 0; i < n; ++i) {
s += S[i];
s += "#";
}
n = s.length();
int center = 0, right = 0,answer = 0;
vector<int> p;
p.resize(n);
for (int i = 0; i < n; ++i) {
int ii = (center << 1) - i;
for (p[i] = (i < right)?min(p[ii], right - i):0; (i - p[i] - 1 >= 0) && (i + p[i] + 1 < n) && (s[i - p[i] - 1] == s[i + p[i] + 1]); ++p[i])
;
if (i + p[i] > right) {
right = i + p[i];
center = i;
}
answer = max(answer, p[i]);
}
return answer;
}
int main() {
gets(S);
printf("%d\n",run(S, strlen(S)));
return 0;
}
原题链接： http://www.patest.cn/contests/pat-a-practise/1040
投递淘天集团等公司10个岗位 >
