PAT1040. Longest Symmetric String (25)(回文串：dp)-白红宇

PAT1040. Longest Symmetric String (25)(回文串：dp)

阅读量：6275 次

发布时间：2019-06-22

本文共 1721 字，大约阅读时间需要 5 分钟。

题意：

给出一个字符串，求出其中最大的回文串字数

要点：

这题比较好的办法是用dp做：

dp[i][j]表示从s[i]到s[j]是否为回文串，用0、1区分

s[i]=s[j]时，dp[i][j]=dp[i+1][j-1]；s[i]!=s[j]时，dp[i][j]=0

边界：dp[i][i]=1，dp[i][i+1]=(s[i]==s[i+1])?1:0

因为i、j如果从小到大的顺序来枚举的话，无法保证更新dp[i][j]的时候dp[i+1][j-1]已经被计算过。因此不妨考虑按照字串的长度和子串的初试位置进行枚举，即第一遍将长度为3的子串的dp的值全部求出，第二遍通过第一遍结果计算出长度为4的子串的dp的值…这样就可以避免状态无法转移的问题

#include
    
     #include
     
      #include
      
       #include
       #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;const int INF = 0xfffff;const int maxn = 1010;int dp[maxn][maxn];int main() { string s; getline(cin, s); int ans = 1; int len = s.length(); for (int i = 0; i < len; i++) { dp[i][i] = 1; if (i + 1 < len&&s[i] == s[i + 1]) { dp[i][i + 1] = 1; ans = 2; } } for (int l = 3; l <= len; l++) { for (int i = 0; i+l-1 < len; i++) { int j = i + l - 1; if (s[i] == s[j] && dp[i + 1][j - 1] == 1) { dp[i][j] = 1; ans = l; } } } cout << ans << endl; return 0;}

/*以字符串中每个字符为对称轴*/#include
    
     #include
     
      #include
      
       #include
       #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;const int INF = 0xfffff;const int maxn = 1005;int main() { string s; getline(cin, s); int len = 1; for (int i = 0; i < s.size(); i++) { for (int j = 0; j <= min(i, (int)(s.size() - i - 1)); j++) { string s2 = s.substr(i - j, 2 * j + 1);//字数为奇数 string s3 = s2; reverse(s3.begin(), s3.end()); if (s2 == s3&&s2.size() > len) len = s2.size(); string s4 = s.substr(i - j, 2 * j + 2);//字数为偶数 string s5 = s4; reverse(s5.begin(), s5.end()); if (s4 == s5&&s4.size() > len) len = s4.size(); } } cout << len << endl; return 0;}