HDU - 4513
题目：http://acm.hdu.edu.cn/showproblem.php?pid=4513
我写过一篇将我对Manacher算法理解的blog：https://blog.csdn.net/weixin_43191865/article/details/90451240
这一题只需要在判断回文串的时候加上一句：ma[i - mp[i]] <= ma[i - mp[i] + 2]
即可
代码：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn = 1e5 + 7; int s[maxn], ma[maxn*2],n; int mp[maxn*2]; void Manacher() { int l = 0; ma[l++] = -1; ma[l++] = -2; for (int i = 0; i < n; i++) { ma[l++] = s[i]; ma[l++] = -2; } ma[l] = 0; int maxx = 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]] && ma[i - mp[i]] <= ma[i - mp[i] + 2]) { mp[i]++; } if (i + mp[i] > mx) { mx = i + mp[i]; id = i; } maxx = maxx > mp[i] ? maxx : mp[i]; } printf("%d\n", maxx - 1); } int main() { int T; cin >> T; while (T--) { cin >> n; for (int i = 0; i < n; i++) scanf("%d", s + i); Manacher(); } return 0; }
HDU - 3294
题目：http://acm.hdu.edu.cn/showproblem.php?pid=3294
解法：只需要在马拉车的基础上加入max_id , maxx 记录 mp[max_id]的最大值。
这个时候输出的那两个下标就等于：
（max_id-(maxx-2)-1)/2 (max_id+(maxx-2)-1)/2
化简即可
代码：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn = 2e5 + 7; char s[maxn], ma[maxn * 2]; int mp[maxn * 2]; void Manacher(int flag) { int l = 0; ma[l++] = '$'; ma[l++] = '#'; int end = strlen(s); for (int i = 0; i < end; i++) { ma[l++] = s[i]; ma[l++] = '#'; } ma[l] = 0; int maxx = 0, max_id = 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; } if (maxx < mp[i]) { maxx = mp[i]; max_id = i; } } int j; if (maxx == 2) { printf("No solution!\n"); } else { printf("%d %d\n", (max_id - maxx + 1) / 2 , (max_id + maxx - 3 ) / 2 ); for (int j = max_id - mp[max_id] + 2; j <= max_id + mp[max_id]-2; j+=2) { printf("%c", ma[j]-flag>='a'?(char)(ma[j]-flag):(char)(ma[j]+26-flag)); } printf("\n"); } } int main() { char ss[10]; int flag; while (scanf("%s", ss)!=EOF) { flag = ss[0] - 'a'; scanf("%s", s); Manacher(flag); } return 0; }
