KS10. 回文字符串
描述
输入描述
每个测试用例输入一行字符串（由数字0-9，字母a-z、A-Z构成），字条串长度大于0且不大于1000.输出描述
输出该字符串的最长回文子串的长度。（不要求输出最长回文串，并且子串不要求连续）示例1
输入:
adbca
输出:
3
说明:
因为在本题中，不要求回文子串连续，故最长回文子串为aba(或ada、aca)C++ 解法, 执行用时: 3ms, 内存消耗: 484KB, 提交时间: 2019-08-09
#include<iostream>
#include<algorithm>
#include<string>
#include<math.h>
#include<stdlib.h>
#include <iostream>
#include <vector>
#include <queue>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<iostream>
#include<set>
#include<map>
using namespace std;
int dp[2][1500];
int main()
{
string str;
cin>>str;
int len = str.length();
memset(dp,0,sizeof(dp));
int cur = 0;
for(int i = len - 1; i >= 0; i--)
{
cur ^= 1;
dp[cur][i] = 1;
for(int j = i + 1; j < len; j++)
{
if(str[i] == str[j])
dp[cur][j] = dp[cur^1][j-1] + 2;
else
dp[cur][j] = max(dp[cur][j-1],dp[cur^1][j]);
}
}
cout<<dp[cur][len-1];
return 0;
}
C++14 解法, 执行用时: 3ms, 内存消耗: 492KB, 提交时间: 2020-05-18
#include<iostream>
#include<algorithm>
#include<string>
#include<math.h>
#include<stdlib.h>
#include <iostream>
#include <vector>
#include <queue>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<iostream>
#include<set>
#include<map>
using namespace std;
int dp[2][1500];
int main()
{
string str;
cin>>str;
int len = str.length();
memset(dp,0,sizeof(dp));
int cur = 0;
for(int i = len - 1; i >= 0; i--)
{
cur ^= 1;
dp[cur][i] = 1;
for(int j = i + 1; j < len; j++)
{
if(str[i] == str[j])
dp[cur][j] = dp[cur^1][j-1] + 2;
else
dp[cur][j] = max(dp[cur][j-1],dp[cur^1][j]);
}
}
cout<<dp[cur][len-1];
}
C++ 解法, 执行用时: 3ms, 内存消耗: 500KB, 提交时间: 2020-11-17
#include<iostream>
#include<algorithm>
#include<string>
#include<math.h>
#include<stdlib.h>
#include <iostream>
#include <vector>
#include <queue>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<iostream>
#include<set>
#include<map>
using namespace std;
int dp[2][1500];
int main()
{
string str;
cin>>str;
int len = str.length();
memset(dp,0,sizeof(dp));
int cur = 0;
for(int i = len - 1; i >= 0; i--)
{
cur ^= 1;
dp[cur][i] = 1;
for(int j = i + 1; j < len; j++)
{
if(str[i] == str[j])
dp[cur][j] = dp[cur^1][j-1] + 2;
else
dp[cur][j] = max(dp[cur][j-1],dp[cur^1][j]);
}
}
cout<<dp[cur][len-1];
return 0;
}
C++ 解法, 执行用时: 3ms, 内存消耗: 504KB, 提交时间: 2020-07-28
#include<iostream>
#include<algorithm>
#include<string>
#include<math.h>
#include<stdlib.h>
#include <iostream>
#include <vector>
#include <queue>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<iostream>
#include<set>
#include<map>
using namespace std;
int dp[2][1500];
int main()
{
string str;
cin>>str;
int len = str.length();
memset(dp,0,sizeof(dp));
int cur = 0;
for(int i = len - 1; i >= 0; i--)
{
cur ^= 1;
dp[cur][i] = 1;
for(int j = i + 1; j < len; j++)
{
if(str[i] == str[j])
dp[cur][j] = dp[cur^1][j-1] + 2;
else
dp[cur][j] = max(dp[cur][j-1],dp[cur^1][j]);
}
}
cout<<dp[cur][len-1];
return 0;
}
C++ 解法, 执行用时: 3ms, 内存消耗: 608KB, 提交时间: 2020-04-23
#include<iostream>
#include<algorithm>
#include<string>
#include<math.h>
#include<stdlib.h>
#include <iostream>
#include <vector>
#include <queue>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<iostream>
#include<set>
#include<map>
using namespace std;
int dp[2][1500];
int main()
{
string str;
cin>>str;
int len = str.length();
memset(dp,0,sizeof(dp));
int cur = 0;
for(int i = len - 1; i >= 0; i--)
{
cur ^= 1;
dp[cur][i] = 1;
for(int j = i + 1; j < len; j++)
{
if(str[i] == str[j])
dp[cur][j] = dp[cur^1][j-1] + 2;
else
dp[cur][j] = max(dp[cur][j-1],dp[cur^1][j]);
}
}
cout<<dp[cur][len-1];
}