找到字符串第一个匹配项的下标

找到字符串第一个匹配项的下标

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

示例 1：

输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。

示例 2：

输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。

提示：

• 1 <= haystack.length, needle.length <= 104
• haystack 和 needle 仅由小写英文字符组成

题解

这个题可以使用暴力算法，但是一直暴力似乎没有意思，不好玩，可以尝试一下KMP（烤馍片）算法。

KMP的精髓就是确定一个next数组，从而可以在不匹配的时候回退，我这里先用前缀表的方式来求一下next数组。

1. 前缀表是什么

   其实这里的前缀表是记录的是最长公共前后缀，这里的前缀和后缀采用的是真前缀和真后缀。

   例如字符串 aabaaf ，他的前缀可以表示为 a , aa , aab , aaba , aabaa，后缀可以表示为 f , af , aaf , baaf , abaaf

2. 怎么求前缀表

   看了很多博客，似乎对next有了一个朦胧的认知，求next数组本来也是n-1个KMP算法，并且有点动态规划的韵味。Ok，来看怎么求next数组

   vector<int> getnext(string needle)  //是要对模式串进行next
      {
          vector<int>next(needle.size(),0); //初始化next数组
          int j=0;
          for(int i=1;i<needle.size();i++)  //这里的i表示后缀末尾，j表示前缀末尾
          {
              while(j>0 && needle[j]!=needle[i])  // j要确保大于0，当不相等的时候，就回退到前一个
              {
                  j=next[j-1];
              }
              if(needle[i]==needle[j])
              j++;
              next[i]=j;  // 赋值
          }
      }
   

   让我们看看这个代码的执行过程，字符串为 aabaaf

i	j	前缀	后缀	字符串	是否相等	next[i]
1	0	a	a	aa	aa	1
2	1	aa	ab	aab	a!=b(下标为2)
2	1	aa	ab	aab	j=0，不执行while	0
3	0	a	a	aaba	aa	1
4	1	aa	aa	aabaa	aa(下标为1和4)	2
5	2	aab	aaf	aabaaf	b!=f
6	0	a	f	aabaaf	j=0，不执行while	0

最终得到的next为 0 1 0 1 2 0

感觉这个和最长回文子串 – 柚子茶 差不多，都是从最小长度开始，然后根据上一次的结果来计算

3. 根据前缀表来进行匹配

   假设主串S=“aabaabaaf”,子串T=“aabaaf”，我们已经有了T的前缀表，在匹配中我们发现，

   

   这里f出错了，那么我们就可以根据a的next进行回退，为什么呢？因为a的next数值为2，就意味着最长相等全后缀为2，就变成了这样

   

​ 匹配成功！

以下是完整代码

class Solution {
public:
    vector<int> getnext(string needle)
    {
        vector<int>next(needle.size(),0);
        int j=0;
        for(int i=1;i<needle.size();i++)
        {
            while(j>0&&needle[j]!=needle[i])
            {
                j=next[j-1];
            }
            if(needle[i]==needle[j])
            j++;
            next[i]=j;
        }
        return next;
    }
    int strStr(string haystack, string needle) {
        if(needle.size()==0)  //为空直接返回
        return -1;
        vector<int>next;
        next = getnext(needle);
        int j=0;
        for(int i=0;i<haystack.size();i++)
        {
            while(j>0 && haystack[i]!=needle[j]) //回退
            {
                j=next[j-1];
            }
            if(haystack[i]==needle[j]) 
            {
                j++;
            }
            if(needle.size()==j) //找到，返回下标
            return i-j+1;
        }
        return -1;
    }
};