java - Spoj 上的代码提交出现运行时错误 (NZEC)

Question

我正在努力解决 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);
        }
}
}

Answer 1

运行时错误的原因是:

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++;
}

因为现在你在计算前缀函数时最多做一次跳跃，这是不正确的。