九度筆記之 1252：回文子串

題目描述：
輸入一個字符串，輸出該字符串中對稱的子字符串的最大長度。

比如輸入字符串“google”，由於該字符串裡最長的對稱子字符串是“goog”，因此輸出4。

輸入：

存在多組數據，每組數據一行字符串，長度不大於100。

輸出：

輸出回文子串的最大長度。

樣例輸入：

google

樣例輸出：

4

算法分析：
 本來打算用《最長合法括號序列1》中的算法，利用動態規劃做，但是對於例如“aaa”的情況該算法就無效了

 因為括號必須是左右一對同時出現，左邊的必為”(“，右邊的必為”)“，所以當出現str[pos]==”(”或 str[sympos]<0 或str[sympos]==”)”的情況時，str[pos]位置的符號不可能再和dp[pos-1]合法子括號序列的子字符串構成合法括號序列。

(()(

)()(

())

)())

對於回文字符串，則會出現以下情況

aaa  

      dp[1]=2 ,   

      pos==2時，sympos== -1,得到dp[pos]=1 實際上dp[pos]=3

       因為a[1]相當於一個回文字符串，str[0]==str[2]，dp[pos]=3

abadabad

      dp[6]=7,    

      pos==8時，sympos== -1,得到dp[pos]=1 實際上dp[pos]=5

      因為abadaba中的子字符串aba為一個回文字符串，str[3]==str[7],故dp[pos]=5

公共子序列查找

新的思路就是，如果字符串s中含有回文字符串，回文字符串一定為該字符串的逆序列rs和該字符串s的公共子序列，如下所示。

      google        s

  elgoog      sr   

                 abamngnm    s

                       mngnmaba   sr

  mngnmaba       sr

 算法實現就很簡單了，從sr的某個位置開始，s從0開始逐個字符比較，記錄最長的公共序列。

源代碼：
程序中需要注意的是srbegin的每次循環，temLen都要重新置為0

srid的每次循環結束後，也要判斷一下temLen和maxLen的大小，

 google      s

elgoog       sr

在sid==3,srid==5時，

sr.at(srid)==s.at(sid)

temLen++;

srid++;sid++;

循環退出，此時temLen==4,maxLen==0

還有就是考慮到sr需要前向錯位，後向錯位來比較，所以需要將s,sr反過來比較一下。參看int getMaxNum(std::string &s)

#include <iostream>
#include <string>
using namespace std;
int getMaxNum(std::string &s,std::string &sr){
    int sLen = s.size();
    int maxLen = 0;
    int temLen = 0;
    /*
     *   google   s
     * elgoog    sr
     */
    /*
     * abacdefgfedcmnm
     * mnmcdefgfedcaba
     */
    int srbegin = 0;
    while(srbegin < sLen){// sr start from i compare s
        int srid = srbegin;
        int sid = 0;
        temLen = 0;  //attention
        while(srid < sLen){
            if(sr.at(srid)==s.at(sid)){
                temLen++;
            }else{
                if(temLen > maxLen)
                    maxLen = temLen;
                temLen=0;
                //break;
            }
            srid++;
            sid++;
        }//while(srid < sLen)
        if(temLen>maxLen)     //attention srid==sLen must be considered for "google"
            maxLen = temLen;
        srbegin++;
    }
    return maxLen;
}
 
int getMaxNum(std::string &s){
    std::string sr(s.rbegin(),s.rend());
    int maxLen = 0;
    maxLen = getMaxNum(s,sr);
    int rMaxLen = getMaxNum(sr,s);
    if(rMaxLen>maxLen)
        return rMaxLen;
    else
        return maxLen;
}
 
 
void test(){
    std::string s = "ab";
    std::string sr(s.rbegin(),s.rend());
    std::cout<<sr<<std::endl;
}
void judo(){
    std::string s;
    //int temLen = 0;
    while(std::cin>>s){
        std::cout<<getMaxNum(s)<<std::endl;
    }
}
int main() {
    //cout << "!!!Hello World!!!" << endl; // prints !!!Hello World!!!
    judo();
    return 0;
}
 
/**************************************************************
    Problem: 1252
    User: KES
    Language: C++
    Result: Accepted
    Time:10 ms
    Memory:1520 kb
****************************************************************/