字符串基础 学习笔记

字符串 $Hash$

Hash 是一种将一个字符串映射为一个数字的算法,它可以帮助我们在 $O(1)$ 的时间内判断两个字符串是否相等,或进行回文判断。但 $Hash$ 也有一定的出错概率。当数据范围为 $10^5$ 级别时可能会出现哈希冲突，可以使用双模数哈希。

基础 $hash$

时间复杂度:$O(1)$

对于一个长度为 $n$ 的字符串,它的哈希值为 $\sum_{i=1}^{i\le n} s_i\times base^{n-i} \bmod P$ 。其中 $base$ 和 $P$ 自选。

具体实现：

• 对于一个字符串 $S$ ,它的每一个位前缀哈希值就等于上一位前缀哈希值 $H_{i-1}\times base +s_i$。
• 预处理出 $base$ 的 $1\sim n$ 次方 $Pow_{1\sim n}$
• 对于一段区间 $[l,r]$ ,它的 $hash$ 值即为 $H_r-H_{l-1}\times Pow_{r-l+1}$

代码实现:

// 字符串基础 学习笔记
// 基础 hash 具体实现
unsigned long long h[1e5 + 10], pow[1e5 + 10];

bool check(int l, int r) {  //查询区间Hash值
  return h[r] - h[l - 1] * pow[r - l + 1];
}

void init_hash(char* s) {  //初始Hash映射数组
  int n = strlen(s);
  for (int i = 1; i <= n; ++i) {
    h[i] = h[i - 1] * base + s[i];  //套公式
  }
}

void Init_pow() {
  pow[0] = 1;
  for (int i = 1; i <= Maxn; ++i)
    pow[i] = pow[i - 1] * base;  //初始 base 幂
}

允许失配 k 次的匹配

时间复杂度:$O(nklogn)$

具体实现:
枚举子串,每次二分+hash 找到第一个不同的位置,从这个位置之后继续匹配。

代码实现：暂无

$KMP$ 模式串匹配

时间复杂度：$O(n)$

$KMP$ 算法是一个在线性时间内完成字符串匹配的算法。

具体实现：

• $nxt$ 数组维护在文本串每一位最长的前缀等于后缀的长度
• 当 $nxt$ 数组维护到第 $i$ 位时，
  如果 $s_{nxt_i+1}=s_{i+1}$ 就把 $nxt$ 数组 $+1$，
  否则让 $nxt$ 数组 跳 $nxt$。
• 匹配时直接暴力拓展,失配时跳 $nxt$ 而不是从头开始。

代码实现：

// 字符串基础 学习笔记
// KMP 模式串匹配具体实现
//s 是模式串, s1 是文本串, Ans 记录匹配成功的位置
int nxt[Maxn];
void init(char* s) {
  int n = strlen(s + 1);
  for (int i = 2, j = 0; i <= n; ++i) {
    while (j && s[j + 1] != s[i])  //如果第 i 位失配了,就跳 nxt
      j = nxt[j];
    if (s[j + 1] == s[i]) ++j;  //可以匹配成功就 +1
    nxt[i] = j;
  }
}
vector< int > Ans;
void check(char* s, char* s1) {
  int n = strlen(s + 1), m = strlen(s1 + 1);
  for (int i = 1, j = 0; i <= m; ++i) {
    while (j && s[j + 1] != s1[i])  //失配就跳 nxt
      j = nxt[j];
    if (s[j + 1] == s1[i]) ++j;  //可以匹配就暴力拓展
    if (j == n) {
      Ans.push_back(i - n + 1);  //匹配成功就计入答案
      j = nxt[j];
    }
  }
}

$Manacher$ 回文匹配

时间复杂度：$O(n)$

$Manacher$ 是通过维护 $R$ 和 $mid$ 在线性时间内求一个模式串最长回文子串的算法，但它有一个明显的缺点就是只能判断长度为奇数的回文串，所以要在读入时进行特殊字符补位操作。

证明:

由于 R 是单调递增的，所以时间复杂度也是线性的。

具体实现：

• 在读入时先将第一位设为 ‘@’ 防止数组越界，后将读入字符和补 ‘#’ 交替进行，方便判偶数长度。
• 每到一位都要维护两个信息以便下次拓展，分别是这一位及以前所有回文子串右端点最大值 $R$ 和拓展 $R$ 到当前值的 $mid$。
• 更新第 i 位时先继承回文半径为 $i$ 关于 $mid$ 的 对称点 $j$ 的答案和 $i$ 到 $R$ 的距离中的最小值，后暴力拓展，同时更新 $R$ 和 $mid$。

代码实现：

// 字符串基础 学习笔记
// Manacher 回文匹配具体实现
int scan(char* s) {
  char c = ' ', s[0] = '~', s[1] = '#', int cnt = 1;  //先补特殊字符防止越界
  while (c < 'a' || c > 'z') c = getchar();
  while (c >= 'a' && c <= 'z')
    s[++cnt] = c, s[++cnt] = '#', c = getchar();  //补位和读入交替进行
  return cnt;                                     //返回字符串长度
}

int manacher(char* s, int n) {
  int R = 0, pos, ans = 0;
  for (int i = 1; i <= n; ++i) {
    if (i <= R) r[i] = min(r[(pos << 1) - i], R - i + 1);  //先继承
    while (s[i - r[i]] == s[i + r[i]]) r[i]++;             //后暴力拓展
    if (i + r[i] > R) R = i + r[i] - 1, pos = i;           //能更新就更新
    if (r[i] > ans) ans = r[i];                            ///更新答案
  }
  return ans;
}

字符串 $Trie$

详见

本文作者：CloudySky
写作时间： 2021-08-12
最后更新时间： 2021-10-09
遵循协议： BY-NC-SA