题目链接
http://acm.hdu.edu.cn/showproblem.php?pid=3068
思路 n^3 的做法 对于每个字符 同时 往左往右搜 但是要分奇偶 就是 n^3 n^2 的做法 将字符串处理一下 变成全都是奇数的 字符串
比如
abab
变成
“#a#b#a#b#”
这样 如果原串是回文 这样处理后 也是回文
n 的做法 Manacher 算法 参考 https://segmentfault.com/a/1190000003914228
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, b) memset(a, (b), 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; typedef pair<string, int> psi; typedef pair<string, string> pss; const double PI = acos(-1.0); const double E = exp(1.0); const double eps = 1e-30; const int INF = 0x3f3f3f3f; const int maxn = 1e5 + 1e4 + 10; const int MOD = 1e9 + 7; char Ma[maxn<<1]; int Mp[maxn<<1]; void Manacher(char s[], int len) { int l = 0; Ma[l++] = '$'; Ma[l++] = '#'; for (int i = 0; i<len; i++) { Ma[l++] = s[i]; Ma[l++] = '#'; } Ma[l] = 0; int mx = 0, id = 0; for (int i = 0; i<l; i++) { Mp[i] = mx>i ? min(Mp[2 * id - i],mx - i) : 1; while (Ma[i + Mp[i]] == Ma[i - Mp[i]])Mp[i]++; if (i + Mp[i]>mx) { mx = i + Mp[i]; id = i; } } } char s[maxn]; int main() { while (~scanf(" %s", s)) { int m = strlen(s); Manacher(s, m); int ans = 0; m = (m<<1) + 2; for (int i = 0; i < m; i++) ans = max(ans, Mp[i]); printf("%d\n", ans - 1); } }转载于:https://www.cnblogs.com/Dup4/p/9433110.html
