[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










注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 会员标识 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-20 00:05
门头沟学院_2023
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议