Implement strStr().

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Update (2014-11-02):

The signature of the function had been updated to return the index instead of the pointer. If you still see your function signature returns a char
* or String, please click the reload button  to
reset your code definition.

算法：KMP算法，字符串比对

java：

public class Solution {

    public int strStr(String haystack, String needle) {

        int l1=haystack.length();

        int l2 = needle.length();

        if(l1<l2){

            return -1;

        }

        if(l1==l2){

            if(haystack.equals(needle)){

                return 0;

            }

            return -1;

        }

        if(l2==0){

            return 0;

        }

        int i=0;

        int j=0;

        int[] next = new int[l2+1];

        getNext(needle,next);

        while(i<l1&&j<l2){

            if(j==-1||haystack.charAt(i)==needle.charAt(j)){

                i++;

                j++;

            }else{

                j = next[j];

            }

            if(j==l2){

                return i-l2;

            }

        }

        return -1;

    }

    public void getNext(String s, int[] next){

        int i,j;

        int len = s.length();

        i=0;

        j=-1;

        next[0]=-1;

        while(i<len-1){

            if(j==-1||s.charAt(i)==s.charAt(j)){

                i++;

                j++;

                next[i]=j;

            }else{

                j=next[j];

            }

        }

    }

}