当前位置: 代码迷 >> 综合 >> PAT1040. Longest Symmetric String (25)(回文串:dp)
  详细解决方案

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

热度:67   发布时间:2024-01-16 13:22:33.0

题意:

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

要点:

这题比较好的办法是用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<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<sstream>
#include<functional>
#include<algorithm>
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<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<sstream>
#include<functional>
#include<algorithm>
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;
}


  相关解决方案