HDU5384-Hotaru's problem-Manacher

找出紧挨的三个回文串,例如abccbaabc ,形如ABA格式,其中AB为回文串。计算最长的长度。

首先用Manacher处理回文半径。然后就是找到两个点,都是偶数的回文串,并且共享了中间一段。

之后拿set搞一下就可以了= =

 #include <set>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue> using namespace std; const int maxn = 1e5+;
int Ma[maxn<<],Mp[maxn<<];
set <int> pos; struct node{
int mp,p;
node(){}
bool operator < (const node &rhs) const
{
if(mp == rhs.mp) return p > rhs.p;
else return mp < rhs.mp;
}
}; priority_queue<node> pq;
void Manacher(int s[],int len)
{
int l = ;
Ma[l++] = '$';
Ma[l++] = '#';
for(int i=;i<len;i++)
{
Ma[l++] = s[i];
Ma[l++] = '#';
}
Ma[l] = ;
int mx = ,id = ;
for(int i=;i<l;i++)
{
Mp[i] = mx > i? min(Mp[*id-i],mx-i) : ;
while(Ma[i + Mp[i]] == Ma[i-Mp[i]]) Mp[i]++;
if(Mp[i] + i > mx)
{
mx = Mp[i] + i;
id = i;
}
}
} int T,N;
int save[maxn];
int main()
{
scanf("%d",&T);
int cas = ;
while(T--)
{
scanf("%d",&N);
for(int i=;i<N;i++) scanf("%d",&save[i]);
Manacher(save,N);
int ans = ;
node tmp;
while(!pq.empty()) pq.pop();
pos.clear();
for(int i=;i<*N+;i++)
{
if(Ma[i] == '#' && Mp[i] > )
{
tmp.mp = Mp[i];
tmp.p = i;
pq.push(tmp);
}
}
int cnt = ;
//for(int i=0;i<2*N+1;i++) printf("%d\t",i); puts("");
//for(int i=0;i<2*N+1;i++) printf("%c\t",Ma[i]=='#'?'#':Ma[i]+'0'); puts("");
//for(int i=0;i<2*N+1;i++) printf("%d\t",Mp[i]); puts("");
while(!pq.empty())
{
tmp = pq.top(); pq.pop();
int cur = tmp.p,mp = tmp.mp;
//printf("cur:%d mp:%d\n",cur,mp);
int tmp_pos = ;
if(cnt)
{
auto it = pos.lower_bound(cur - (mp-) ); //printf("L:%d ",*it);
if(it != pos.end() && *it >= cur-(mp-)) ans = max(ans,cur-*it); it = pos.lower_bound(cur + (mp-) ); it--;
//printf("R:%d\n",*it);
if(it != pos.end() && *it <= cur+(mp-)) ans = max(ans,*it-cur);
}
pos.insert(cur);
cnt++;
}
printf("Case #%d: %d\n",++cas,ans/*);
}
}
上一篇:利用beans.xml进行简单的Spring应用上下文创建与使用


下一篇:【传输协议】TCP、IP协议族之数字签名与HTTPS详解