↓ Skip to main content
111qqz’s blog
  1. Tags/

Manacher

2016

hdu 4513 吉哥系列故事——完美队形II (回文串,manacher)

·473 words·1 min
ACM Manacher
题目链接：hdu4513 题意：给出一个n的数的序列，求出一个最长的回文字串，并且满足从[l,mid]单调增（非严格单调，可以相等），[mid,r]单调减（同样是可以相等） 思路：manacher…int型的也是可以搞的。。要求单调的话。。。while扩展的时候判一下就好了。。。

poj 3294 Girls' research (manacher,回文串)

·1257 words·3 mins
ACM Manacher
poj 3294 题意：先做个简单替换，然后求替换后的字符串的最长回文串，以及这个最长回文串的开始和结束位置。 思路：manacher。需要注意的是，返回下标的时候如果字符串长度为偶数，那么中间是没有字符的，需要特判一下（我的做法是 left+(ans%2==0)）。

poj 3974 Palindrome (最长回文字串，manacher裸题)

·297 words·1 min
ACM Manacher
poj3974 题意：求最大长度的回文字串。 思路：manacher裸题，用来练习算法。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年04月18日 星期一 16时32分25秒 4File Name :code/poj/3974.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <ctime> 19#define fst first 20#define sec second 21#define lson l,m,rt<<1 22#define rson m+1,r,rt<<1|1 23#define ms(a,x) memset(a,x,sizeof(a)) 24typedef long long LL; 25#define pi pair < int ,int > 26#define MP make_pair 27 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=2E6+7; 34char st[2*N]; 35int p[2*N]; 36 37int manacher(char *s) 38{ 39 int len = strlen(s); 40 for ( int i = len ; i >= 0 ; i-- ) 41 { 42 s[i+i+2]=s[i]; 43 s[i+i+1]='#'; 44 } 45 s[0]='$'; 46 47 int id = 0 ; 48 int maxlen = 0 ; 49 50 for ( int i = 2 ; i < 2*len+1 ; i++) 51 { 52 if (id+p[id]>i) p[i] = min(p[2*id-i],id+p[id]-i); 53 else p[i] = 1; 54 55 while (s[i+p[i]]==s[i-p[i]]) p[i]++; 56 if (id+p[id]<i+p[i]) id = i; 57 if (p[i]>maxlen) maxlen = p[i]; 58 } 59 return maxlen-1; 60} 61int main() 62{ 63 #ifndef ONLINE_JUDGE 64 freopen("code/in.txt","r",stdin); 65 #endif 66 int cas = 0 ; 67 while (scanf("%s",st)!=EOF) 68 { 69 if (st[0]=='E'&&st[1]=='N'&&st[2]=='D') break; 70 printf("Case %d: %d\n",++cas,manacher(st)); 71 72 } 73 74 #ifndef ONLINE_JUDGE 75 fclose(stdin); 76 #endif 77 return 0; 78}