2 tiger1334 tiger1334 于 2016.01.29 17:50 提问

我的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();
}
}

2个回答

devmiao
devmiao   Ds   Rxr 2016.01.29 22:31

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

tiger1334
tiger1334   2016.01.29 23:36

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

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!