[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










全部评论

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务