題目描述

??????? 輸入一個字符串，求出其中最長的回文子串。子串的含義是：在原串中連續出現的字符串片段。回文的含義是：正著看和倒著看相同。如abba和yyxyy。在判斷回文時，應該忽略所有標點符號和空格，且忽略大小寫，但輸出應保持原樣（在回文串的首部和尾部不要輸出多余字符）。輸入字符串長度不超過5000，且占據單獨的一行。應該輸出最長的回文串，如果有多個，輸出起始位置最靠左的。

輸入

一行字符串，字符串長度不超過5000。

輸出

字符串中的最長回文子串。

樣例輸入

Confuciuss say:Madam,I'm Adam.

樣例輸出

Madam,I'm Adam

提示

?

樣例說明：Madam,I'm Adam去掉空格、逗號、單引號、忽略大小寫為MADAMIMADAM，是回文。

?

算法分析一：?
首先解決“判斷時忽略標點，輸出進卻要按原樣”的問題？ 可以用一個簡單的方法：預處理。構造一個新字符串，不包含原來的標點符號，而且所有字符變成大寫（順便解決了大小寫的問題）。用到的函數：?
（1）isalpha(c)用來檢查c是否為字母，如果是字母，則返回1；否則返回0。
（2）isdigit(c)用來檢查c是否為數字（0～9），如果是數字，則返回1；否則返回0。
（3）toupper(c)用來將c字符轉換為大寫字母，返回c對應的大寫字母。
（4）tolower(c)用來將c字符轉換為小寫字母，返回c對應的小寫字母。
下面來枚舉回文串的起點和終點，然后判斷它是否真的是回文串。
int max=0;
for(i = 0; i < m; i++)
? ?for(j = i; j < m; j++)
? ? ? ?if(s[i..j]是回文串 && j-i+1 > max) max = j-i+1;
“當前最大值”變量max，它保存的是目前為止發現的最長回文子串的長度。如果串s的第i個字符到第j個字符（記為s[i..j]）是回文串，則檢查長度j-i+1是否超過max。
判斷s[i..j]是否為回文串的方法如下：
int ok = 1;
for(k = i; k <= j; k++)
? ? if(s[k] != s[i+j-k]) ? ok = 0;
s[k]的“對稱”位置是s[i+j-k]，因為只要一次比較失敗，就應把標記變量ok置為0。
最后的問題：原樣輸出。
??? 由于在求max值時，不知道s[i]和s[j]在原串buf中的位置。因此，必須增加一個數組p，用p[i]保存s[i]在buf中的位置。在預處理得到，然后在更新max的同時把p[i]和p[j]保存到x和y，最后輸出buf[x]到buf[y]中的所有字符。
不足：當輸入字符串較長時，容易超時，因枚舉回文起點和終點，循環過多。

算法分析二：枚舉回文串的“中間”位置i，然后不斷往外擴展，直到有字符不同。提示：長度為奇數和偶數的處理方式是不一樣的。

WA原因：運行錯誤60%

沒有分析出原因，codeup也沒有樣例可以過....好煩！

#include <iostream> #include <cstring> #include <algorithm> using namespace std;const int maxn = 5005; char S[maxn], Scopy[maxn], pos[maxn]; int dp[maxn][maxn]; int n; int a , b; //記錄兩個端點 int main() {gets(S);int len = strlen(S), ans = -1;int index = 0;for(int i =0; i < len; i++){if(S[i] >= 'A' && S[i] <= 'Z'){pos[index] = i;Scopy[index++] = S[i]-'A'+'a';//存放在原來的位置}else if(S[i] >= 'a' && S[i] <= 'z'){pos[index] = i;Scopy[index++] = S[i];}//大寫轉小寫}int lenC = strlen(Scopy);memset(dp,0,sizeof(dp));for(int i = 0; i < lenC; i++){dp[i][i] = 1;if(i < lenC - 1){if(Scopy[i] == Scopy[i+1]){dp[i][i+1] = 1;ans = 2;a = i;b = i+1;}}}int i, j;for(int L = 3; L < lenC; L++){for(i = 0; i + L - 1 <= lenC; i++){j = i+L-1;if(Scopy[i] == Scopy[j] && dp[i+1][j-1] == 1){dp[i][j] = 1; // if(ans == L) // { // if(a > i) // { // ans = L; // a = i; // b = j; // }else continue; // }else // {ans = L;a = i;b = j; // }}}}for(int k = pos[a]; k <= pos[b]; k++){printf("%c", S[k]);} // printf("%d\n", ans);return 0; }

?

總結

以上是生活随笔為你收集整理的Codeup-问题 A: 【字符串】最长回文子串的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。