KMP?next数组？前缀表？菜鸟重拾C++之算法

本文主要是介绍KMP?next数组？前缀表？菜鸟重拾C++之算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

实现strStr（）

知识点

• KMP（Knuth-Morris-Pratt）算法是一种用于字符串匹配的高效算法。其原理基于字符串匹配时的特性，通过预处理模式字符串（待匹配字符串）的信息，避免在匹配过程中重复比较已经匹配过的部分。

• 前缀表记录了模式字符串中最长相同前后缀的长度

  前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串。

  后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。

  最长相同前后缀的长度：

  举一个例子“ABABBABC”

  • A -> 0

  • AB -> 0

  • ABA -> 1

  • ABAB -> 2

  • ABABB -> 0

  • ABABBA->0

  • ABABBAB->2

  • ABABBABC->0

  再举个栗子“aabaaf”

  • a->0

  • aa->1

  • aab->0

  • aaba->1

  • aabaa->2

  • aabaaf->0

• next 数组 其实就是前缀表的不同表现形式，主流的写法有三种：

  拿“aabaaf”来说，需要找到aabaabaaf的匹配下标

  第一种next数组表示方式为[0, 1, 0, 1, 2, 0]， 当他遍历到f的时候发现f和b有冲突，那么找到f对应的前缀表位置的前一位的值为2，那么之前回退到前缀表下标为2的地方。

  第二种next数组表示方式为[-1, 0, 1, 0, 1, 2]，当他遍历到f的时候发现f和b有冲突，那么找到f对应的前缀表位置的值为2，那么之前回退到前缀表下标为2的地方。

  第三种next数组表示方式为[-1, 0, -1, 0, 1, -1]，当他遍历到f的时候发现f和b有冲突，那么找到f对应的前缀表位置的前一位的值为1，加1之后，那么之前回退到前缀表下标为2的地方。

• 难点：next 数组怎么写

  我们就看第一种 next 数组的写法

  • 初始化

  • 前后缀不相等的情况

  • 前后缀相等的情况

  • 更新 next 数组

  /* i:表示后缀末尾；j表示前缀末尾（也表示冲突返回的下标位置）*/// 初始化
  int j = 0;
  next[0] = 0;
  ​
  for(int i = 1; i < s.size(); i++){// 前后缀不相等的情况, 根据不变性原理，j也需要回退到j对应的前一位的值对应的下标值的位置while(j > 0 && s[i] != s[j]){j = next[j - 1];}// 前后缀相等的情况if(s[i] == s[j]){// 更新next数组next[i] = j++;}
  }

题目

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

28. 找出字符串中第一个匹配项的下标 - 力扣（LeetCode）

题解1：暴力解法

class Solution {
public:int strStr(string haystack, string needle) {for (int i = 0; i + needle.size() <= haystack.size(); i++) {//i + needle.size() <= haystack.size()if (haystack[i] == needle[0]) {bool flag = true;int j = needle.size() - 1;for (; j >= 0; j--) {if (haystack[i + j] != needle[j]){flag = false;break;}}if(flag ){ // 善用flagreturn i;}}}return -1;}
};

题解2：KMP解法

class Solution {
public:void getNext(int* next, const string& s){int j = 0;next[0] = 0;for(int i = 1; i < s.size(); i++){while(j > 0 && s[i] != s[j]){j = next[j - 1];}if(s[i] == s[j]){j++;}next[i] = j;}}
​int strStr(string haystack, string needle) {if(needle.size() == 0) return 0;int next[needle.size()];getNext(next, 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(j == needle.size()){return (i - needle.size() + 1);}}return -1;}
};

这篇关于KMP?next数组？前缀表？菜鸟重拾C++之算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---