专栏首页vblogPAT1040 Longest Symmetric String (25分) 中心扩展法+动态规划

PAT1040 Longest Symmetric String (25分) 中心扩展法+动态规划

题目

Given a string, you are supposed to output the length of the longest symmetric sub-string. For example, given Is PAT&TAP symmetric?, the longest symmetric sub-string is s PAT&TAP s, hence you must output 11.

Input Specification: Each input file contains one test case which gives a non-empty string of length no more than 1000.

Output Specification: For each test case, simply print the maximum length in a line.

Sample Input:

Is PAT&TAP symmetric?

Sample Output:

11

题目解析

给定一个字符串,要求输出它最长回文子串的长度。

什么是回文子串,就是类似 baab aacaa这种中心对称的字符串。

注意,输入字符串可能包括空格,所以这里使用getline(cin,str)

思路一:中心扩展法

所谓中心扩展法,就是从回文串“中心对称”这个特点来的。

我们先分析一下这个“对称”,如果是奇数长度的字符串,那么它关于最中心的那个字符对称;如果是偶数长度的字符串,它的对称线是最中心两个字符的中间画一条线(比如baab),也就是关于最中心两个字符(aa)是对称的(那两个字符是一样的)

所以中心扩展法的思路就是,把某个位置作为中间位置,向两边扩展,直到左右指针对应位置字符不等

那么对于一个字符串,中心位置如何取,如果以每个字符作为中心,那么我们就能找到它所有长度为奇数的最长对称串的长度,以连续两个字符(相同)作为中心,救能得到所有长度为偶数的最长的对称串的长度,然后我们再二者之间取最大值即可

文字描述比较抽象,直接看代码,挺容易理解的。

#include <iostream>
using namespace std;

// 中心扩展法
int helper(string s, int leftborder,int l,int r,int rightborder) {
    // 向两端无限扩展
    while(leftborder <= l && s[l] == s[r] && r <= rightborder) {
        --l;++r;
    }
    // 已记录的有效回文串长度
    return r - l - 1;
}
int main() {
    string s;
    getline(cin, s);
    int len = s.length();
    int res = 0;
    for (int i = 0; i < len; ++i) {
        // 以本身为中心,像左右扩展
        int len1 = helper(s, 0, i, i, len - 1);
        // 以自己和下一个字符为中心,向左右扩展
        int len2 = helper(s, 0, i, i + 1, len - 1);
        res = max(res, len1);
        // 总是取更大那个
        res = max(res, len2);
    }
    cout << res;
}

思路二:动态规划

思路一里面对于每个字符都要进行两次中心扩展,肯定进行了很多次重复操作,而动态规划就是为解决重复操作而生的。

把一个字符串表示为 s[0],s[1]...s[i],s[i+1],s[i+2]...s[j-2],s[j-1],s[j]...s[len-1]

  • 如果 s[i+1,j-1] 是回文串,那么只要 s[i] == s[j],就可以确定 s[i][j] 也是回文串
  • 长度为12时的子串需单独判断
  • dp[i][j] 代表 s[i][j] 是不是回文子串

动态规划的核心就是由子问题状态保留,不再重新计算,对于一个长度为len的字符串,它的每个子串长度可以是 1到len,我们从小到大取出所有长度的子串进行判断。

#include<iostream>
using namespace std;

int main() {
    string s;
    getline(cin, s);
    int len = s.length();
    int res = 0;
    bool dp[len][len] = {false};
    int maxLen = 0;
    //对于所有长度的子串
    for (int len = 1; len <= s.length(); len++) 
        for (int i = 0; i < s.length(); i++) {
            int j = i + len - 1; // i是起点,j是终点,长度是len
            // 当前情况不可能,不存在从i开始长为len的子串
            if (j >= s.length()) break; 
            //长度是1就是单个字符,满足回文
            if (len == 1) dp[i][j] = true; 
            // 长度是2就看这两个字符是否相等
            else if (len == 2) dp[i][j] = s[i] == s[j];
            // 否则,如果 S[i+1,j-1] 是回文串,只要 S[i] == S[j],S[i][j]也是回文串
            else dp[i][j] = dp[i + 1][j - 1] && s[i] == s[j];
            // 当前串是回文串且比上一次的更长
            if (dp[i][j] && len > maxLen) { 
                maxLen = len;
            }
        }
    cout << maxLen;
    return 0;
}

感觉动态规划会比中心扩展更快,但提交结果是中心扩展更快,真是脑壳痛。。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • PAT 1001 A+B Format (20分) to_string()

    Calculate a+b and output the sum in standard format -- that is, the digits must ...

    vivi
  • PAT 1021 Deepest Root (25分) 从测试点3超时到满分再到代码优化

    A graph which is connected and acyclic can be considered a tree. The height of t...

    vivi
  • PAT 1015 Reversible Primes (20分) 谜一般的题目,不就是个进制转换+素数判断

    A reversible prime in any number system is a prime whose "reverse" in that numbe...

    vivi
  • 2019HDU多校赛第二场 HDU 6599 I Love Palindrome String(回文树+哈希判回文)

    题意:多组输入string,判断长度从1 到 len(string)的字串中有 多少 回文串,且前 一半也为回文

    用户2965768
  • 【LeetCode题解-005】Longest Palindrome Substring

    Given a string s, find the longest palindromic substring in s. You may assume th...

    周三不加班
  • 你见过数组的这种骚操作吗?

    注意看printf那一行,发现什么了没有?竟然有i[a]这样的操作?然后你运行一下还会发现,结果完全正常。

    编程珠玑
  • 寻找次大元素

    汐楓
  • HYSBZ 2565 最长双回文串 (回文树)

    2565: 最长双回文串 Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 1377  Solved: 714 ...

    ShenduCC
  • 08:Challenge 1

    总时间限制: 10000ms单个测试点时间限制: 1000ms内存限制: 262144kB描述 给一个长为N的数列,有M次操作,每次操作是以下两种之一: (1)...

    attack
  • 【leetcode】Two Sum

    Given an array of integers, find two numbers such that they add up to a specific...

    阳光岛主

扫码关注云+社区

领取腾讯云代金券