字符串基础

定义

字符串就是一个字符序列。通常用 0-based 索引：

索引:	0	1	2	3	4	5
字符:	a	b	a	b	c	a

长度记为 n，空串长度为 0。

概念

基础概念

对于字符串 S = “ababca”：

概念	定义	例子
字符	单个字符	“b”, “a”, “c”…
子串	任意连续的一段	S[1..3] = “bab”
前缀	从开头取一段	“a”, “ab”, “aba”, “abab”…
后缀	从结尾往前取一段	“a”, “ca”, “bca”, “abca”…

组合概念

概念	定义
真子串	原串中包含的子串
真前缀	不包括原串本身的前缀
真后缀	不包括原串本身的后缀
Border	既是真前缀又是真后缀的子串

存储

C风格

C中一般用字符数组char[]存储字符串

char str[] = "ababca";

数组中最后一个字符是空字符 \0，表示字符串的结束。

C++风格

C++中一般用std::string类存储字符串

std::string str = "ababca";

std::string 类提供了很多方便的操作字符串的方法。

哈希

将字符串映射为整数的操作。

BKDR哈希

把键看作 $base$ 进制的整形，计算其十进制值为哈希值。

公式

$H(s) = \sum_{i=1}^{n} s_i \times base^{n-i}$

通常取大质数作为$base$，如$131$。 有时候也用 s[i] - 'a'作为分量

代码

int hash(string s){
    int base = 131, res = 0;
    for(int i = 0;i < s.size();i++)
        res = res * base + s[i];
    return res;
}

子串哈希

基于BKDR哈希，用于 $O(1)$ 计算子串的哈希值的方法。

公式

• 前缀哈希值 $H(s_{0..i}) = \sum_{j=0}^{i} s_j \times base^{i-j}$
• 子串哈希值 $H(s_{l..r}) = H(s_{0..r +1}) - H(s_{0..l}) \times base^{r-l+1}$

哈希值	分量
$H_{0..r+1}$	$s_0\times base^r$	…	$s_{l-1}\times base^{r-l+1}$	$s_l\times base^{r-l}$	…	$s_r$
$H_{0..l}$	$s_0\times base^{l-1}$	…	$s_{l-1}$	-
$H_{l..r}$	-			$s_0\times base^{l-1}$	…	$s_{r}$

代码

vecetor<int> preH; // H[0..i-1]
vector<int> powB; // base^i
// 预处理前缀哈希值和base的幂
void init(string s, int base){
    powB.push_back(1); // base^0
    preH.push_back(0); // H(0..-1) = 0
    for(int i = 0;i < s.size();i++){
        powB.push_back(powB[i] * base);
        preH.push_back(preH[i] * base + s[i]);
    }
}
int hash(int l, int r){
    return preH[r+1] - preH[l] * powB[r-l+1];
}

字符串匹配

概念

• 主串：要查找的长字符串
• 模式串：主串中的目标子串
• 匹配：在主串中找到模式串的位置

基本方法

• 暴力匹配：逐个字符比较
• KMP算法：利用前缀表
• BM算法：利用坏字符和好后缀
• Sunday算法：利用坏字符
• Rabin-Karp算法：利用哈希

BF算法（Brute Force）

基本思想

通过在主串中逐个尝试可能的匹配位置，每次比较整个模式串。

步骤

• 初始化指针 i j，指向主串和模式串的起始位置。
• i 指针遍历主串，搜索匹配位置。
• j 指针遍历模式串，比较字符。
• 重置 j 指针，移动 i 指针，继续搜索。

代码

vector<int> BF(string t, string p){
    vector<int> res;
    for(int i = 0;i < t.size();i++){
        for(int j = 0;j < p.size();j++) 
           if(t[i+j] != p[j]) break;
        if(j == p.size()) res.push_back(i);
    }
    return res;
}

复杂度

• 时间复杂度：$O(nm)$，其中 $n$ 为主串长度，$m$ 为模式串长度。
• 空间复杂度：$O(1)$，不使用额外空间。

Rabin-Karp算法

基本思想

利用哈希函数将模式串、主串的子串映射为整数，快速比较哈希值

步骤

• 预处理所有前缀哈希值
• 计算模式串的哈希值
• 遍历主串，$O(1)$ 计算每个子串的哈希值并比较

代码

// 预处理同上述子串哈希预处理
void preprocess(string &p){...}
int hash(int l, int r){...}
// 匹配
vector<int> RK(string &t, string &p){
    // 预处理
    vector<int> res;
    preprocess(p);
    // 计算模式串哈希值
    int hashP = 0;
    for(char c: p) hashP = hashP * base + c;
    // 滑动窗口匹配
    for(int i = 0;i <= t.size() - p.size();i++){
        int hashT = hash(i, i + p.size() - 1);
        if(hashT == hashP) {
            // 可能存在哈希冲突，验证字符串
            for(int j = 0;j < p.size();j++)
                if(t[i+j] != p[j]) break;
            if(j == p.size()) res.push_back(i);
        }
    }
    return res;
}