我正在努力解决 Spoj 上的运行时错误 (NZEC) 问题, http://www.spoj.com/problems/NHAY/
我从我这边尝试了很多案例,每次它在 eclipse 中给出正确的输出,但在 Spoj 上提交时无法找出运行时错误的原因,任何人都可以帮我解决这个错误。
这是我的代码,
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
class KMP {
public int[] lps(String needle, int needleLength)
{
int lps[] = new int[needleLength];
int j=0,i=1;
lps[0]=0;
while(i<needle.length())
{
if(needle.charAt(j) == needle.charAt(i))
{
lps[i] = j+1;
i++;
j++;
}
else
{
if(j != 0)
{
j = lps[j-1];
}
lps[i] = 0;
i++;
}
}
return lps;
}
public List<Integer> KMPalgo(String hayStack, String needle, int needleLengh)
{
int lps[] = lps(needle, needleLengh);
int i=0;
int j=0;
List<Integer> position = new ArrayList<Integer>();
while(i<hayStack.length())
{
if(hayStack.charAt(i) == needle.charAt(j))
{
i++;
j++;
}
else
{
if(j !=0)
{
j = lps[j-1];
}
else
i++;
}
if(needle.length() == j)
{
position.add(i-j);
if(j !=0)
j = lps[j-1];
}
}
return position;
}
public static void main(String[] args) throws NumberFormatException, IOException {
KMP o = new KMP();
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
while(true)
{
String needlLength = bf.readLine().trim();
if(needlLength == null || needlLength.equals(""))
break;
int lNeedle = Integer.parseInt(needlLength);
String needle = bf.readLine().trim();
String haystack = bf.readLine().trim();
List<Integer> result= o.KMPalgo(haystack, needle, lNeedle);
System.out.println();
for(Integer itr : result)
System.out.println(itr);
}
}
}
最佳答案
运行时错误的原因是:
String needlLength = bf.readLine().trim();
if(needlLength == null || needlLength.equals(""))
break;
在检查 needlLength
是否为 null
之前调用 trim()
。
但看起来您至少还有一个错误。你应该更换
if(j != 0)
{
j = lps[j-1];
}
lps[i] = 0;
i++;
与
if(j != 0)
{
j = lps[j-1];
}
else
{
lps[i] = 0;
i++;
}
因为现在你在计算前缀函数时最多做一次跳跃,这是不正确的。
关于java - Spoj 上的代码提交出现运行时错误 (NZEC),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/45423319/