关于数据结构与算法:字符串KMP算法字符串哈希

KMP 算法个别用于字符串匹配问题
例如：给出两个字串 S，P 须要判断 P 串是否为 S 串的子串

前缀：蕴含第一个字符不蕴含最初一个字符
后缀：蕴含最初一个字符不蕴含最初一个字符
例如：aaba
前缀别离为：a, aa, aab
后缀别离为：a, ba, aba
最长相等前后缀：记录前缀和后缀相等的长度，在这个例子中最长相等前后缀为 a，长度为 1
在 KMP 算法当中，用一个 next 数组记录每个字符的最长相等前后缀
例如：aabaa
前缀别离为：a, aa, aab, aaba
后缀别离为：a, aa, baa, abaa
next 数组为：a:0, aa:1, aab:0, aaba:1, aabaa:2
next = [0, 1, 0, 1, 2]

暴力解法中，咱们须要两重循环遍历 P 串和 S 串，直到找到匹配的字串，工夫复杂度为 O(n*m)，n，m 别离示意 P 串和 S 串的长度
KMP 算法的核心思想就是用前缀表记录曾经匹配过的文本内容，使得当产生匹配抵触的时候，能够不须要从新遍历，而是通过前缀表回退到之前匹配胜利过的地位持续匹配，next 数组就是前缀表
具体原理参考 https://www.bilibili.com/vide…

结构 next 数组分为四步：
初始化
定义两个指针 i，j
j 指向前缀开端地位，i 指向后缀开端地位
next 数组初始化为 0，j 从 0 开始，i 从 1 开始
解决前后缀不雷同的状况
以后后缀不相等并且 j >0 时（后续要回退到 j - 1 的状态所以要保障 j >0）
j 回退到 j - 1 的状态
解决前后缀雷同的状况
前后缀雷同时，j 向后挪动一位
更新 next 数组
将 next 数组更新为 j

代码模板

int j = 0;
next[0] = 0;
for (int i = 1; i < m; i ++){while (j > 0 && s[i] != s[j]) j = next[j - 1];
  if (s[i] == s[j]) j ++;
  next[i] = j;
}

链接 https://leetcode.cn/problems/…

leetcode 解题代码

class Solution {
public:
  int strStr(string haystack, string needle) {int n = haystack.length(), m = needle.length();
      vector<int> next(m);
      int j = 0;// 初始化 j
      next[0] = 0;// 初始化 next 数组
      for (int i = 1; i < m; i ++){// 初始化 i
          while (j > 0 && needle[i] != needle[j]) j = next[j - 1];// 前后缀不雷同时
          if (needle[i] == needle[j]) j ++;// 前后缀雷同时
          next[i] = j;// 更新 next 数组
      }

      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;
  }
};

链接 https://leetcode.cn/problems/…

leetcode 解题代码

class Solution {
public:
  bool repeatedSubstringPattern(string s) {int n = s.size();
      vector<int> next(n);
      int j = 0;
      next[0] = 0;
      for (int i = 1; i < n; i ++){while (j > 0 && s[i] != s[j]) j = next[j - 1];
          if (s[i] == s[j]) j ++;
          next[i] = j;
      }
      return next[n - 1] != 0 && n % (n - next[n - 1]) == 0;
  }
};

求两个字符串的子串是否雷同

字符串的映射
例如：有一个 ’abcdefgycr’ 的字符串，将其映射成某个哈希值并用数组 h 存下来
h[n]示意字符串第 n 位的哈希值
h[0]=0，h[1]=’a’ 的哈希值，h[2]=’ab’ 的哈希值 …
哈希值的定义
例如：字符串 ’abcd’ 的哈希值是多少呢？
咱们把 ’abcd’ 看成 p 进制的数，那么 ’abcd’ 则能够示意为
a*p^3+b*p^2+c*p^1+d*p^0
然而这样映射的值可能过大，所以咱们再将其取模 q
这样就能够将字符串映射到 0~q- 1 之间
个别状况下 p =131，q=2^64，能够假设不会产生哈希抵触 >.<（感兴趣的能够查一下）
定义一个区间 [L, R] 的哈希值
通过上述形式咱们曾经晓得了 h[L-1]和 h[R]
通过 h[R] – h[L-1]*p^(R-L+1)

typedef unsigned long long ULL;// 能够省略取模的步骤了

const int P = 131;

ULL h[N], p[N];

// 初始化
p[0] = 1;// p^0 = 1
h[0] = 0;
// 前缀和定义前缀字符串哈希
for (int i = 1; i <= n; i ++){h[i] = h[i - 1] * P + str[i];
    p[i] = p[i - 1] * P;
}
// 计算字串 [L, R] 的哈希值
ULL get(int l, int r){return h[r] - h[l - 1] * p[r - l + 1];
}

链接 https://leetcode.cn/problems/…
解题思路：求两个字符串的哈希值，比拟对应段是否相等
为了不必求解两次字符串哈希，能够将两个字符串拼接

leetcode 解题代码

typedef unsigned long long ULL;

const int N = 210, P = 131;
ULL h[N], p[N];

class Solution {
public:
  ULL get(int l, int r) {return h[r] - h[l - 1] * p[r - l + 1];
  }

  bool rotateString(string A, string B) {if (A.size() != B.size()) return false;
      string s = ' ' + A + B;
      int n = s.size() - 1;
      p[0] = 1;
      for (int i = 1; i <= n; i ++) {p[i] = p[i - 1] * P;
          h[i] = h[i - 1] * P + s[i];
      }

      for (int k = 1; k < A.size(); k ++ )
          if (get(1, k) == get(n - k + 1, n) && get(k + 1, A.size()) == get(A.size() + 1, n - k))
              return true;
      return false;
  }
};

解题参考：https://www.acwing.com/
刷题程序参考：https://www.programmercarl.com/

关于数据结构与算法:字符串KMP算法字符串哈希

KMP 算法

利用场景

前缀表

前缀表在 KMP 算法中的作用

next 数组的实现（前缀表实现）

leetcode.28

leetcode.459

字符串前缀哈希

利用场景

利用办法

实现办法

leetcode.796