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

思路

将匹配串的第一个字符进行对比，匹配上后，进行后续字符的对比；

解题方法

1.第一个解决方法：遍历字符串匹配首字符直到源字符串的n-m+1位置，如果匹配上首字符，就切割源字符串长度为m的子串下来与匹配串进行对比；时间复杂度：$O((n-m)\ast m)O((n-m)*m)$,空间复杂度为 $O(1)O(1)$；

2.第二个解决方法：KMP算法，即匹配串会检查之前已经匹配成功的部分中里是否存在相同的「前缀」和「后缀」。如果存在，则跳转到「前缀」的下一个位置继续往下匹配；时间复杂度：$O(n+m)O(n+m)$,空间复杂度为 $O(m)O(m)$；

Code

class Solution {
public:
    int strStr(string haystack, string needle) {
        int m = haystack.size(), n = needle.size();
        if(n==0) return 0;
        vector<int> next(n);//存储前端和后端
        for(int i=1,j=0;i<n;++i)
        {
            while(j>0&&needle[i]!=needle[j])
            {
                j=next[j-1];
            }
            if(needle[i]==needle[j])
            {
                ++j;//匹配上了
            }
            next[i]=j;//不论结果，存入数组
        }

        for(int i=0,j=0;i<m;++i)
        {
            while(j>0&&haystack[i]!=needle[j])
            {
                j=next[j-1];//匹配不上，往前查找
            }
            if(haystack[i]==needle[j])
            {
                ++j;//匹配上了++
            }
            if(j==n)
            {
                return i-n+1;//返回该子串的头部
            }
        }
        return -1;
    }
};