hihocoder 算法-我的hihocoder这个最长回文子串为什么报wrong answer?

问题描述

我的hihocoder这个最长回文子串为什么报wrong answer?

import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
for(int i = 0;i
String str = scanner.next();
System.out.println(findMax(buildStr(str))/2);
}
}
public static int findMax(String str){
int pArr[] = new int[str.length()];
int pr = 0;
int index = 0;
for(int i = 0;i
if(i==0){
pArr[i] = expand(i,str);
pr=pArr[i]+index;
}else{
if(i
if(2*index-i-pArr[2*index-i]>index-pArr[index]){
pArr[i] = 2*index-i-(index-pArr[index]);
index = i;
pr = index+pArr[i];
}else if(2*index-i-pArr[2*index-i]<index-pArr[index]){
pArr[i] = pArr[2*index-i];
}else{
pArr[i] = expandFromPr(i,pr,str);
index = i;
pr = index+pArr[i];
}
}else{
pArr[i] = expand(i,str);
index = i;
pr = index+pArr[i];
}
}
}
int max = 0;
for(int k:pArr){
max = Math.max(k*2-1, max);
}
return max;
}

public static int expandFromPr(int i,int pr,String str){
int count = pr-i;
int j = pr-i;
while(i-j>=0&&i+j<str.length()&&str.charAt(i-j)==str.charAt(i+j)){
j++;
count++;
}
return count;
}

public static int expand(int i,String str){
int count = 1;
int j = 1;
while(i-j>=0&&i+j<str.length()&&str.charAt(i-j)==str.charAt(i+j)){
j++;
count++;
}
return count;
}
public static String buildStr(String str){
StringBuilder strb = new StringBuilder();
int index = 0;
int length = str.length();
length=length*2+1;
for(int i = 0;i<length;i++){
if(i%2==0)
strb.append('#');
else
strb.append(str.charAt(index++));
}
return strb.toString();
}
}

解决方案

你多用几个测试用例测试下,肯定有错的。

解决方案二:

问题是我已经试过了很多用例了,应该怎么想测试用例呢?

时间: 2024-10-22 09:26:15

hihocoder 算法-我的hihocoder这个最长回文子串为什么报wrong answer?的相关文章

lintcode最长回文子串(Manacher算法)

题目来自lintcode, 链接:http://www.lintcode.com/zh-cn/problem/longest-palindromic-substring/ v最长回文子串  给出一个字符串(假设长度最长为1000),求出它的最长回文子串,你可以假定只有一个满足条件的最长回文串. v样例 给出字符串 "abcdzdcab",它的最长回文子串为 "cdzdc". v挑战 O(n2) 时间复杂度的算法是可以接受的,如果你能用 O(n) 的算法那自然更好.

java算法-java求教,算法竞赛入门经典 3.4 最长回文子串

问题描述 java求教,算法竞赛入门经典 3.4 最长回文子串 java新手求教,关键是怎么保存s[i]在buf中的位置,谢谢 解决方案 string longestPalindromeDP(string s) { int n = s.length(); int longestBegin = 0; int maxLen = 1; bool table[1000][1000] = {false}; for (int i = 0; i < n; i++) { table[i][i] = true;

java算法-Longest Palindromic Substring 最长回文子串问题?JAVA

问题描述 Longest Palindromic Substring 最长回文子串问题?JAVA public class Solution { public String longestPalindrome(String s) { String ret = ""; for (int i = 0; i < s.length(); i++) { for (int j = 0; i - j >= 0 && i + j < s.length(); j++)

Longest Palindromic Substring:最长回文子串

题目链接 Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring. 求字符串的最长回文子串 算法1:暴力解法,枚举所有子串,对每个子串判断是否为回文,复杂度为O(n^3) 算法2:删除暴力解法中有很多重复的判

最长公共子序列|最长公共子串|最长重复子串|最长不重复子串|最长回文子串|最长递增子序列|最大子数组和

参考:http://www.ahathinking.com/archives/124.html 最长公共子序列 1.动态规划解决过程 1)描述一个最长公共子序列 如果序列比较短,可以采用蛮力法枚举出X的所有子序列,然后检查是否是Y的子序列,并记录所发现的最长子序列.如果序列比较长,这种方法需要指数级时间,不切实际. LCS的最优子结构定理:设X={x1,x2,--,xm}和Y={y1,y2,--,yn}为两个序列,并设Z={z1.z2.--,zk}为X和Y的任意一个LCS,则:       (1

九度题目1528:最长回文子串

题目1528:最长回文子串 时间限制:1 秒 内存限制:128 兆 特殊判题:否 提交:781 解决:239 题目描述: 回文串就是一个正读和反读都一样的字符串,比如"level"或者"noon"等等就是回文串. 回文子串,顾名思义,即字符串中满足回文性质的子串. 给出一个只由小写英文字符a,b,c...x,y,z组成的字符串,请输出其中最长的回文子串的长度. 输入: 输入包含多个测试用例,每组测试用例输入一行由小写英文字符a,b,c...x,y,z组成的字符串,字

NYOJ 132(最长回文子串)

#include<stdio.h> #include<string.h> #include<ctype.h> #define MAXN 5001 char buf[MAXN],s[MAXN]; int p[MAXN]; int main() { int T,i,j;int len,m,max,x,y; scanf("%d%*c",&T); while(T--) { //fgets(buf,sizeof(buf),stdin); scanf(&

[算法系列之七]Manacher算法之最大回文子串

回文串定义:"回文串"是一个正读和反读都一样的字符串,比如"level"或者"noon"等等就是回文串. 回文子串,顾名思义,即字符串中满足回文性质的子串. 经常有一些题目围绕回文子串进行讨论,比如  HDOJ_3068_最长回文,求最长回文子串的长度.朴素算法是依次以每一个字符为中心向两侧进行扩展, 显然这个复杂度是 O(N^2)的,关于字符串的题目常用的算法有 KMP.后缀数组. AC 自动机,这道题目利用扩展 KMP可以解答,其时间复杂度也

算法:uva 11404 Palindromic Subsequence(LCS回文串,最小字典序)

题目大意 给一个字符串,输出它的最长回文串,如果有多个结果,输出字典序最小的. 思 路 我们都知道把一个字符串逆序后和原字符串进最长公共子序列,可以计算出它的最长回文串长度. 但是这题不仅要输出回文串,而且还要求是字典序最小的,所以挺难搞的. 设str1是正序字符串, str2是逆序后的字符串 f[i][j].len 表示str1的前i位,str2的前j位,最长公共子串的长度 f[i] [j].str 表示str1的前i位,str2的前j位,最长公共子串的最小字典序的字符串 状态转移和正常的LC