【一天一道LeetCode】#28. Implement strStr()

（一）题目

Implement strStr().

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

（二）解题

第一种解法：朴素匹配算法

/*

两个指针，分别指向两个字符串的首字符

如果相等则一起向后移动，如果不同i取第一个相同字符的下一个开始继续匹配

如果最后j等于needle的长度则匹配成功，返回i-j

否则返回0

*/

class Solution {

public:

    int strStr(string haystack, string needle) {

        int j,i;

        for(i = 0 , j =0 ; ihaystack.length()) return -1;

            if(haystack[i]==needle[j]){//如果匹配上就继续向后匹配

                i++;

                j++;

            }

            else{

                i-=j-1;//回溯到匹配开始时needle的首字符对应的下一位

                j=0;//j回溯到needle的首字符

            }

        }

        if(j==needle.length()) return i-j;

        else return -1;

    }

};

第二种解法：KMP模式匹配算法
关于kmp，请自行百度或者大话数据结构P143页

class Solution {

public:

    int strStr(string haystack, string needle) {

        int hlen = haystack.length();

        int nlen = needle.length();

        if(hlen==0) return nlen==0?0:-1;//临界值判断

        if(nlen==0) return 0;//needle为NULL，就直接返回0

        int* next = new int[nlen+1];

        getNext(needle,next);

        int i = 0;

        int j = 0;

        while(i