问题描述
- 我的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();
}
}
解决方案
你多用几个测试用例测试下,肯定有错的。
解决方案二:
问题是我已经试过了很多用例了,应该怎么想测试用例呢?