題目

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:

題目解析

給定一個字符串，要求輸出它最長迴文子串的長度。

什麼是迴文子串，就是類似 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] 也是迴文串
  • 長度爲 1 和 2 時的子串需單獨判斷
  • 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;
}

感覺動態規劃會比中心擴展更快，但提交結果是中心擴展更快，真是腦殼痛。。

相關文章