【Codeforces Global Round 7 D1】Prefix-Suffix Palindrome (Easy version)
Codeforces version round Easy global Palindrome Prefix
2023-09-14 09:03:41 时间
题目链接
翻译
让你选择字符串 \(s\) 的一个前缀和一个后缀(可以为空), 然后拼成一个字符串。
要求这个字符串得是一个回文串,且这个字符串的长度不能超过原串 \(s\) 的前提下最长。
输出这个字符串, easy 版本,长度小于等于 \(5000\)
题解
考虑最后的答案 \(t\),是由 \(s\) 的一个前缀 \(pres\) 和一个后缀 \(afters\) 构成。
又因为 \(t\) 是一个回文串,所以头尾两个蓝色 t'
部分是相同的。
因此,一上来我们可以先用 while (s[l]==s[r])l++,r--
去掉头尾相同的部分(看代码)
然后我们真正要枚举的就是中间的 \(s'\) 部分了,这一部分要么是开头的前缀扩展出来的,要么是后缀往前扩展出来的。
并且 \(s'\) 也要是一个回文串。
有了这个思路,我们就判断一下是前缀还是后缀扩展出来的 \(s'\) 长,加上去就好。
代码
import java.io.*;
import java.util.*;
public class Main {
static InputReader in;
static PrintWriter out;
public static void main(String[] args) throws IOException{
//InputStream ins = new FileInputStream("E:\\rush.txt");
InputStream ins = System.in;
in = new InputReader(ins);
out = new PrintWriter(System.out);
//code start from here
new Task().solve(in, out);
out.close();
}
static int N = 50000;
static class Task{
int t,end1,begin2;
String s;
public boolean ok(int l,int r) {
if (l > r){
return false;
}
while (l <= r){
if (s.charAt(l)==s.charAt(r)){
l++;r--;
}else{
return false;
}
}
return true;
}
public void solve(InputReader in,PrintWriter out) {
t = in.nextInt();
while( (t--) > 0 ){
s = in.next();
int l = 0,r = s.length()-1;
while (l<=r && s.charAt(l)==s.charAt(r)){
l++;r--;
}
if (l > r){
out.println(s);
continue;
}
int mostRihgt = l-1,mostLeft = r+1;
for (int i = l;i<=r;i++){
if (ok(l,i)){
mostRihgt = i;
}
}
for (int i = r;i >= l;i--){
if (ok(i,r)){
mostLeft = i;
}
}
if (l-1>=0) {
out.print(s.substring(0,l));
}
if (mostRihgt-l > r-mostLeft && mostRihgt-l>=0){
out.print(s.substring(l,mostRihgt+1));
}else{
if (r>=mostLeft){
out.print(s.substring(mostLeft,r+1));
}
}
if (r+1<s.length()){
out.print(s.substring(r+1,s.length()));
}
out.println("");
}
}
}
static class InputReader{
public BufferedReader br;
public StringTokenizer tokenizer;
public InputReader(InputStream ins) {
br = new BufferedReader(new InputStreamReader(ins));
tokenizer = null;
}
public String next(){
while (tokenizer==null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(br.readLine());
}catch(IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
}
}
相关文章
- codeforces——Little Pony and Sort by Shift
- 【Educational Codeforces Round 88 (Rated for Div. 2) D】Yet Another Yet Another Task
- 【Codeforces 493C】Vasya and Basketball
- 【Codeforces 427C】Checkposts
- 【Codeforces Round #519 by Botan Investments C】 Smallest Word
- 【CodeForces 353 A】Domino
- 【Codeforces Round #493 (Div. 2) B】Cutting
- 【Educational Codeforces Round 37 C】 Swap Adjacent Elements
- 【Codeforces Round #447 (Div. 2) A】QAQ
- 【codeforces 787B】Not Afraid
- 【codeforces 765C】Table Tennis Game 2
- 【codeforces 764C】Timofey and a tree
- 【codeforces 762B】USB vs. PS/2
- 【codeforces 758B】Blown Garland
- 【codeforces 793D】Presents in Bankopolis
- 【codeforces 755E】PolandBall and White-Red graph
- 【codeforces 801D】Volatile Kite
- 【codeforces 514C】Watto and Mechanism(字符串hash)
- Codeforces Round #435 (Div. 2)