NEFU 1316 Ela的回文串(manacher)

本文主要是介绍NEFU 1316 Ela的回文串(manacher)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Ela在算法课上学习了回文串，但是她不想在回文串中出现她不喜欢的字符。
现在Ela告诉我们她喜欢的字符是{A, H, I, M, O, T, U, V, W, X, Y} 
她想知道对于某个字符串中只包含她喜欢的字符的最长回文子串的长度是多少？

第一行是一个整数T，代表测试样例的个数
接下来T行是T个非空字符串（只包含大写字母），每组样例字符串S的长度小于等于1000，所有样例字符串长度之和小于等于10000。

对于每组测试样例输出一个整数，最长回文串的长度

3
IOIKIOOI
ROQ
WOWMAN

4
1
3

对于第一组样例答案是：IOOI
对于第二组样例答案是：O
对于第三组样例答案是：WOW

DT2131

题意：

中文题。

思路：

比赛时候没有想到把不喜欢的数字都用不同的数字来表示，这样就只需要跑一次马拉车。然后如果碰到是在不喜欢的数字为中心的回文的话就跳过，直接输出在喜欢的数字上的回文的长度就行了。因为以喜欢的数字为回文中心，碰到不喜欢的数字时候，不喜欢的数字都不相同，所以就不会增加回文子串的长度了。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#define MAX_N 2200
using namespace std;
map<char,int>mp;
int N,p[MAX_N];
char str[MAX_N];
int b[MAX_N];
int check(int i)
{if(mp[str[i]]==0)return 0;return 1;
}
void init()
{int i,cnt=1000;for(i=0;str[i];i++){b[2*i+1]=0;if(check(i)==1)b[2*i+2]=(int)str[i];elseb[2*i+2]=++cnt;}N=2*i+1;b[0]=-1,b[N]=b[N+1]=0;
}
void solve()
{int id,maxn=0,ans=0;for(int i=1;i<=N;i++){p[i]=i<maxn?min(maxn-i,p[2*id-i]):1;while(b[i+p[i]]==b[i-p[i]]) ++p[i];if(i+p[i]>maxn) maxn=i+p[i],id=i;ans=max(ans,p[i]-1);}
}
int main()
{int t;scanf("%d",&t);mp['A']=1;mp['H']=1;mp['I']=1;mp['M']=1;mp['O']=1;mp['T']=1;mp['U']=1;mp['V']=1;mp['W']=1;mp['X']=1;mp['Y']=1;mp['#']=1;while(t--){scanf("%s",str);init();solve();int maxn=0;for(int i=1;i<=N;i++){if(b[i]>1000)continue;elsemaxn=max(maxn,p[i]-1);}printf("%d\n",maxn);}return 0;
}

这篇关于NEFU 1316 Ela的回文串(manacher)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！