题目链接
https://www.patest.cn/contests/gplt/L2-008
思路
有两种思路
第一种
遍历每一个字符
然后对于每一个 字符 同时 往左 和 往右 遍历 只要 此时 左右两边所指的字符 相同 就可以继续往下遍历 然后更新答案
但是这种情况 要分 奇数回文 和 偶数回文
有些麻烦
所以 我们能不能 转换成 一种情况
将字符串 格式化 一下就可以了
比如
moom 这个 字符串
在首尾和字符间 加上一个 不会出现的字符 比如 ‘#’
格式化成
“#m#o#o#m#”
这样
然后 就变成了 奇数 回文
就只有一种情况了 就是O(n^2) 的时间复杂度
AC代码
#include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <cmath> #include <climits> #include <ctime> #include <iostream> #include <algorithm> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <numeric> #include <sstream> #include <iomanip> #include <limits> #define CLR(a) memset(a, 0, sizeof(a)) #define pb push_back using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair <int, int> pii; typedef pair <ll, ll> pll; const double PI = 3.14159265358979323846264338327; const double E = exp(1); const double eps = 1e-6; const int INF = 0x3f3f3f3f; const int maxn = 1e3 + 5; const int MOD = 1e9 + 7; int main() { string s; getline(cin, s); string cnt = "#"; int len = s.size(); for (int i = 0; i < len; i++) cnt += s[i], cnt += '#'; len = cnt.size(); int ans = 1; for (int i = 0; i < len; i++) { int temp = 0; if (cnt[i] != '#') temp ++; for (int j = i - 1, l = i + 1; j >= 0 && l < len; j--, l++) { if (cnt[j] == cnt[l]) { if (cnt[j] != '#') temp += 2; } else break; } ans = max(ans, temp); } printf("%d\n", ans); }转载于:https://www.cnblogs.com/Dup4/p/9433175.html
