字符串

CJ_Fu · 2023-01-30 11:17:14 · 个人记录

0 - 定义

string s 或 char s[]。

1 - 字典树(\texttt{Trie})

将 n 个字符串存储在一棵树中。每个字符代表一条边，根节点到每个单词节点经过的所有边代表了所有的字符串。

实现：

const int maxn=2e5+3;
const int maxa=26 +3;

string s;
bool word[maxn];
int ch[maxn][maxa];

int init(int n){ // 建树
    int tot=0;
    for(int i=1;i<=n;i++){
        cin>>s;
        int len=s.length();
        int now=1;
        for(int j=0;j<len;j++){
            int &to=ch[now][s[j]-'a'];
            if(!to)to=++tot;
            now=to;
        }
    }
    return tot;
}

void query(int q){ // 查询
    for(int i=1;i<=q;i++){
        cin>>s;
        int len=s.length();
        int now=0;
        for(int j=0;j<len;j++){
            int &to=ch[now][wd[s[j]]];
            if(!to){ cout<<"0\n"; goto ed; }
            now=to;
        }
        ed:;
    }
}

1.1 - 01 Trie

特殊的 Trie，仅由 01 构成，显然 01 Trie 是一棵二叉树。

而二进制数可以看作 01 串，因此 01 Trie 可以被用于处理某些二进制数的问题。

2 - 字符串匹配问题

2.1 - 单模式串匹配问题

\text{Question 1:}

给定模式串 s 和文本串 t，查询文本串 t 是否在 s 中出现，以及所有的出现位置。

\text{Solution 1:}

暴力匹配 O(|s|) 枚举子串的左端点 i ，然后 O(|t|) 枚举 t 的位置 j 检查是否匹配 (s_i+j-1 = t_j)，最坏复杂度为 O(|s| × |t|) 。

\text{Solution 2(KMP):}

在暴力匹配的过程中，如果发现 j 这个位置不可行，那么 i 就换成 i + 1 然后重新匹配。

如果匹配发现 j 不可行，至少可以确定 t 在 1 到 j - 1 这段范围都是匹配上了的，根据这个信息我们是否可以进行优化？把 i 和 j 换到一个更合适的位置？

这个合适的位置只与 t 和 j 有关而与 s 无关。定义失配指针（或失配函数）fail(j) = k 表示 i, j + 1 失配后 j + 1 换到 k + 1 重新开始匹配。

计算失配函数的时候就是 t 在匹配自己。

2.1.1 - KMP(Knuth-Morris-Pratt)

实现：

const int maxn=2e5+3;
const int maxa=26 +3;

char s[maxn],t[maxn];
int lens,lent;
int fail[maxn];

void init(){
    cin>>s+1; cin>>t+1;
    lens=strlen(s+1); lent=strlen(t+1);
}

void getfail(){
    fail[0]=-1;
    for(int i=0;i<lent;i++){
        int j=fail[i];
        while(~j&&t[j+1]!=t[i+1]) j=fail[j];
        fail[i+1]=j+1;
    }
}
void solve(){
    for(int i=1,j=0;i<=lens;i++){
        while(~j&&s[i  ]!=t[j+1]) j=fail[j];
        j++;
        if(j==lent) cout<<i-lent+1<<'\n', j=fail[j];
    }
}

fail 的性质

$j - fail(j)$ 是 $t(1, j)$ 的最小循环节。将失配指针看作指向父节点的话，失配关系构成一棵树，称为失配树，或 fail 树。 $\text{Solution 3(Hash):}

哈希可以枚举位置然后 O(1) 判断 t 和 s 的一个子串是否相同。

2.1.2 - Hash

将字符串看作 B 进制数，由于数字太大，对 p 取模作为哈希值。

其中 B,p 必须互质。

自然溢出：p = 2^{64}，那么 B 必须是奇数。

如果两个串哈希值相等，就认为这两个串是相同的。

由于可以将字符串转换成数字，哈希值的应用相当广泛。

哈希冲突

如果有两个不同的串哈希值相同，就说这两个串哈希值冲突了。

如果要计算 n 个不同串的哈希值，一般的模型可以假定 n 个哈希值是在 [0,p-1] 的随机数，根据生日悖论相关理论，当 n = O(\sqrt p) 的时候有 O(1) 的概率两个随机数相同。

所以当 p = 10^9 + 7 之类的数的时候其实 n 稍微大一点就会溢出。这个时候可以采用自然溢出或者双模数。

区间哈希值

对于一个串 s 通过预处理快速求一个子串的哈希值。

预处理前缀哈希 h(i) 以及 p(i) = B^i ，那么 [L,R] 的哈希值为

h(R) -h(L -1)p(R -L + 1)

也就是说通过预处理可以 O(1) 求任意子串的哈希值。

\text{Solution 4(ACAM):}

是文本串个数为 1 的特殊情况。

2.2 - 多模式串匹配问题

\text{Question 2:}

给定模式串 s 和 n 个文本串 \{t_i \}，查询每个文本串 t_i 是否在 s 中出现的次数。

\text{Solution 1(KMP):}

使用 KMP 的话，每个文本串都要 O(|s|) ，复杂度是 O(n|s|)。

\text{Solution 2(ACAM):}

将所有文本串建 Trie 树，那么暴力匹配的话就是在 Trie 树上走，如果一个节点失配了，我们可以类似 KMP 定义一个失配指针，指向某个节点，这里的失配指针就可以从一个文本串跳到另一个文本串。

先建出 Trie 树，然后求失配指针。求失配指针的过程与 KMP 是类似的，注意由于失配指针指向的点未必是祖先，但是一定深度变小，因此我们需要 bfs Trie 树上的节点来求失配指针。但是为了保证复杂度以及为了方便，我们可以记 trans(u,c) 表示从 u 节点开始跳 fail 直到能够走 c 字符走到的节点。（直接跳 fail 复杂度不正确）

这个 trans 的关系构成了一张 DAG ，称为字典图，求出字典图，那么匹配的时候就不需要跳 fail 直接走 trans 就可以了。

字符串