028 Implement strStr() 实现 strStr()

实现 strStr()。
返回蕴含在 haystack 中的 needle 的第一个字符的索引，如果 needle 不是 haystack 的一部分则返回 -1 。
例 1:
输入: haystack = "hello", needle = "ll"
输出: 2
例 2:
输入: haystack = "aaaaa", needle = "bba"
输出: -1
详见：https://leetcode.com/problems/implement-strstr/description/

方法一：暴力解法

class Solution {
public:
    int strStr(string s, string p) {
        int ss=s.size();
        int ps=p.size();
        int i=0;
        int j=0;
        while(i<ss&&j<ps)
        {
            if(s[i]==p[j])
            {
                ++i;
                ++j;
            }
            else
            {
                i=i-j+1;
                j=0;
            }
        }
        if(j==ps)
        {
            return i-j;
        }
        return -1;
    }
};

 方法二：KMP算法

class Solution {
public:
    int strStr(string s, string p) {
        int i=0;
        int j=-1;
        int ps=p.size();
        vector<int> next(ps+1);
        next[0]=-1;
        while(i<ps)
        {
            if(j==-1||p[i]==p[j])
            {
                ++i;
                ++j;
                next[i]=j;
            }
            else
            {
                j=next[j];
            }
        }
        int ss=s.size();
        i=0,j=0;
        while(i<ss&&j<ps)
        {
            if(j==-1||s[i]==p[j])
            {
                ++i;
                ++j;
            }
            else
            {
                j=next[j];
            }
        }
        if(j==ps)
        {
            return i-j;
        }
        return -1;
    }
};