【求助】28 Implement strStr()： RUNTIME ERROR

又遇到了毫无头绪的错误，自己电脑上跑一点问题都没有，放到网上就报错，不知道应该怎么调，求助，先谢谢各位了 TAT

题目：Implement strStr().
Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

思路：KMP算法，先计算next数组，再算答案。

报错： Runtime Error
Last executed input:        "mississippi", "issipi"

代码如下：
class Solution {
public:
    int strStr(char *haystack, char *needle) {
        int hL = strlen(haystack), nL = strlen(needle);
        if(nL>hL || hL==0)
            return -1;
        if(nL==0)
            return 0;
        int *next = new int[nL];
        buildNext(needle, next, nL);
/*
        for(int i=0; i<nL; i++){
            cout<<next[i]<<" ";
        }
        cout<<endl;
*/
        int p1=0, p2=0;
        while(p1<hL && p2<nL){
            //cout<<p1<<" "<<p2<<endl;
            if(p2==-1 || haystack[p1]==needle[p2]){
                p1++;
                p2++;
            }
            else{
                p2=next[p2];
            }
        }
        delete next;
        if(p2==nL)
            return p1-p2;
        return -1;
    }
    void buildNext(char * s, int * next, int n){
        int p1 = -1, p2 = 0;
        next[0]=-1;
        while(p2<n){
            if(p1==-1){
                p1++;
                p2++;
                next[p2]=0;
            }
            else if(s[p1]==s[p2]){
                p1++;
                p2++;
                next[p2]=next[p2-1]+1;
            }
            else{
                p1=next[p1];
            }
        }
    }
};

我遇到这种情况时会这么调：

先看出错时的输入："mississippi", "issipi"

那么好，现在往程序的第一行中插入这么一句：
if (strcmp(haystay, "mississippi")==0 && strcmp(needle, "issipi")==0) return what_ever_number;
那么此时一定不会（至少在这个测试用例下）报错了。

如果你将此句放到函数的最后一行，那么肯定还是报错。

因此，你可以试着将此句放入函数中不同的位置，那么肯定会找到一个位置：当你将这句放在该位置之前，没有报错；而放在该位置之后，有报错。这说明错误一定出在这个位置上。

如果错误是出在循环中的话，那么这个方法未必管用，但是这样最起码可以极大地缩小错误的范围，方便调试。

stellari 发表于 2015-4-14 20:01
我遇到这种情况时会这么调：

先看出错时的输入："mississippi", "issipi"

嗯嗯，谢谢。是个方法。

不过我很奇怪为什么本地跑没问题而放到网上就不行了，你知道大概原因不？。。

see_world 发表于 2015-4-15 19:26
嗯嗯，谢谢。是个方法。

不过我很奇怪为什么本地跑没问题而放到网上就不行了，你知道大概原因不？。。

原因太多了，但是说到底都是因为你那里的环境和OJ上在某处出现了不同，包括但不仅限于：

1。代码不同：比如贴错了代码
2。测试用例不同：比如你机器上的测试用例和OJ上的不同。
3。测试环境不同：比如OJ中，要重复创建Solution类对象。如果某解法依赖于Solution类中的一个static变量，而又没有每次对这个static变量进行合理的初始化的话。那么这个static变量在上一次测试用例完成之后的残留值是可能会影响下一个测试用例的。

总之，我认为你还是真正地调试一下比较好，因为这种问题很多时候都是出在你认为绝对不可能出错的地方，光凭理论分析是很难找出问题所在的。

stellari 发表于 2015-4-16 14:30
原因太多了，但是说到底都是因为你那里的环境和OJ上在某处出现了不同，包括但不仅限于：

1。代码不同 ...

可能使本地容错性比较好，所以本地跑没有错。实际上我的代码有个地方溢出了：给next[n]赋了值，到网上测编译不过。

谢谢你的帮助！