NEFU 1316 Ela的回文串(manacher)

2024-04-09 13:08
文章标签 回文 nefu manacher 1316 ela

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

Ela的回文串

Problem:1316
Time Limit:1000ms
Memory Limit:65535K

Description

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

Input

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

Output

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

Sample Input

3
IOIKIOOI
ROQ
WOWMAN

Sample Output

4
1
3

Hint

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

Source

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)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/888229

相关文章

csu1328(近似回文串)

题意:求近似回文串的最大长度,串长度为1000。 解题思路:以某点为中心,向左右两边扩展,注意奇偶分开讨论,暴力解即可。时间复杂度O(n^2); 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring>#include<string>#inclu

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

NYOJ 37 回文字符串(记忆化搜索)

OJ题目 : 戳这里~~ 描述 所谓回文字符串,就是一个字符串,从左到右读和从右到左读是完全一样的,比如"aba"。当然,我们给你的问题不会再简单到判断一个字符串是不是回文字符串。现在要求你,给你一个字符串,可在任意位置添加字符,最少再添加几个字符,可以使这个字符串成为回文字符串。 输入 第一行给出整数N(0<N<100) 接下来的N行,每行一个字符串,每个字符串长度不超过1000.

leetcode: 5. 最长回文子串

5. 最长回文子串 题目链接https://leetcode.cn/problems/longest-palindromic-substring/ 题目描述 给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 示例 1: 输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。 示例 2:

java常用算法之最长回文子串(Longest Palindromic Substring)

方法一:时间复杂度为O(n^3) public static String longestPalindrome1(String s) {int maxPalinLength = 0;String longestPalindrome = null;int length = s.length();// check all possible sub stringsfor (int i = 0; i

力扣-9. 回文数

文章目录 力扣题目代码工程方法1:方法2: 力扣题目 给你一个整数 x ,如果 x 是一个回文整数,返回 true ;否则,返回 false 。 回文数 是指正序(从左向右)和倒序(从右向左)读都是一样的整数。 例如,121 是回文,而 123 不是。 示例 1: 输入:x = 121 输出:true 示例 2: 输入:x = -121 输出:false 解释:从左

psd面试(最长回文子序列+动态规划);

点击打开链接 链接:https://www.nowcoder.com/acm/contest/90/D来源:牛客网 题目描述 掌握未来命运的女神 psd 师兄在拿了朝田诗乃的 buff 后决定去实习。 埃森哲公司注册成立于爱尔兰,是一家全球领先的专业服务公司,为客户提供战略、咨询、数字、技术和运营服务及解决方案。他们立足商业与技术的前沿,业务涵盖40多个行业,以及企业日常运营部门的各个

代码随想录刷题day23丨39. 组合总和,40.组合总和II, 131.分割回文串

代码随想录刷题day23丨39. 组合总和,40.组合总和II, 131.分割回文串 1.题目 1.1组合总和 题目链接:39. 组合总和 - 力扣(LeetCode) 视频讲解:带你学透回溯算法-组合总和(对应「leetcode」力扣题目:39.组合总和)| 回溯法精讲!_哔哩哔哩_bilibili 文档讲解:https://programmercarl.com/0039.%E7%

后缀数组 - 求最长回文子串 + 模板题 --- ural 1297

1297. Palindrome Time Limit: 1.0 second Memory Limit: 16 MB The “U.S. Robots” HQ has just received a rather alarming anonymous letter. It states that the agent from the competing «Robots Unlim

数论 - 算数基本定理的运用 --- nefu 118 : n!后面有多少个0

题目链接: http://acm.nefu.edu.cn/JudgeOnline/problemshow.php   Mean:   略。 analyse:  刚开始想了半天都没想出来,数据这么大,难道是有什么公式? 首先我们要知道一点:n!里面所有的0都是2*5得来的,而且不管怎样2的数量一定是>5的数量,所以我们只需要考虑有多少个5就可。 后面也是看了解题报告才知道有