28. 找出字符串中第一个匹配项的下标

[Ni-Guvara]

class Solution {
public:
    int strStr(string haystack, string needle) {

        int len_h = haystack.size();
        int len_n = needle.size();
        // next数组
        int next[len_n];
        getNext(next,needle);

        int p_next = 0;
        for(int idx = 0; idx < len_h ;idx++ )
        {

            while(p_next > 0 && haystack[idx]!=needle[p_next] )
                p_next = next[p_next - 1];

            if(haystack[idx] == needle[p_next])
            {
                ++p_next;
                if(p_next >= len_n)
                    return idx - len_n + 1;
            }

        }
        return -1;
    }

    // next数组
    void getNext(int * next,string & needle)
    {
       int j = 0;
       next[0] = 0;

       for(int i = 1; i < needle.size();i++)
       {
           while(j > 0 && needle[i] != needle[j])
           {
               j = next[j-1];
           }
           if(needle[i] == needle[j])
           {
               ++j;
           }
           next[i] = j;
       }
    }    
};

[rocksc30]

class Solution {
    public int strStr(String haystack, String needle) {

        char[] hc = haystack.toCharArray();
        char[] nc = needle.toCharArray();

        int i = 0, j = 0;
        while(i < hc.length){
            if(hc[i] == nc[j]){
                i++; j++;
            }else{
                i = i - j + 1;
                j = 0;
            }

            if(j == nc.length){
                return i - j;
            }
        }
        return -1;
    }
}