暴力

KMP

RabinKarp

假设主串为s，模式串为pattern
RabinKarp算法的思想就是，将模式串通过哈希函数映射为一个哈希值，然后计算在主串中与模式串相同长度的子串（我在这里将其定义为一个窗口）的哈希值，如果窗口哈希值与模式串的哈希值相等，那么再逐个比较字符串中的每个字符是否相同，如果相同，返回窗口第一个元素的下标，反之窗口右移一位，继续比较，直到剩余元素少于模式串的长度为止。

使用哈希映射就必然会存在哈希值冲突的问题，因此采用除留余数法来降低出现冲突的概率

除留余数法的性质：如果在每次操作后都将结果除以Q并取余，等价于在完成了所有算术运算后再将最后的结果除以Q并取余。

image.png

  1. // 检查字符串是否匹配
  2. bool check(string s, string pattern, int i) {
  3.     for (int j = 0; j < pattern.size() && i + j < s.size(); j++) {
  4.         if (pattern[j] != s[i + j])
  5.             return false;
  6.     }
  7.     return true;
  8. }
  10. // 计算从索引0开始长度为m的子串的哈希值
  11. long long computeHash(const string &s, const int &len, const long long &q, const int &R) {
  12.     long long hashValue = 0;
  13.     for (int i = 0; i < len; i++) {
  14.         hashValue = (hashValue * R + s[i]) % q;
  15.     }
  16.     return hashValue;
  17. }
  19. // RabinKarp算法
  20. int RabinKarp(string s, string pattern) {
  21.     int n = s.size();
  22.     int m = pattern.size();
  23.     if (m > n)
  24.         return -1; // 不匹配
  26.     int R = 256;
  27.     long long q = 1000000006; // q 是一个很大的素数
  28.     long long patHash = computeHash(pattern, m, q, R); // 计算模式串的哈希值
  29.     long long sHash = computeHash(s, m, q, R);
  31.     if (patHash == sHash && check(s, pattern, 0))
  32.         return 0; // 匹配成功
  34.     // 如果第一次没配成功的话执行下面的操作
  35.     long long rm = 1; // 用于减去窗口第一个字符
  36.     for (int i = 0; i <= m - 1; i++) {
  37.         rm = (rm * R) % q;
  38.     }
  40.     for (int i = m; i < n; i++) {
  41.         sHash = ((sHash + q - rm * s[i - m]) % q) % q;  // 连续取两次是为了减少冲突的概率，可以不减
  42.         sHash = (sHash * R + s[i]) % q;
  44.         if (sHash = patHash && check(s, pattern, i - m + 1))
  45.             return i - m + 1;
  46.     }
  48.     return -1;
  49. }