简单字符串 学习笔记

目录

1. 字符串哈希

2. 字典树

3. 字典树的倒序建树

4. KMP

正文

1. 字符串哈希

1.1 基础

可以在数字和字符串之间快速转化。

考虑一个哈希函数：\(f(s)=(\sum\limits_{i=0}^{n}s_i\times base^{n-i+1})\)。

容易发现这些值是唯一的。但是取模时需要选一个较大模数，减少冲突概率。

const ll mod=1e10+19,base=100073;
string s;
ll gethash(string s) {
    ll ans=0;
    for(int i=0; i<=(int)s.size(); i++) ans=(ans*base+(int)s[i])%mod;
    return ans;
}

1.2 字符串哈希做 KMP

显然可以预处理出 \(base^i\) 及其逆元，然后指针移动的时候改哈希值判断即可。

2. 字典树

2.1 定义

设 \(tr_{i,j}\) 表示第 \(i\) 个节点经过 \(j\) 指向的位置。

2.2 插入和删除

插入时，对于每个点，如果未访问则新开一个点，如果已经访问过则往下跳。
同时，维护 ans 数组表示这个点经过的次数。有时候需要维护 vis 数组表示这个位置是不是一个字符串的末尾。

void insert(string s) {
    int x=0;
    for(int i=0; i<(int)s.size(); i++) {
        if(!t[x][get(s[i])]) t[x][get(s[i])]=++cnt;
        x=t[x][get(s[i])],ans[x]++;
    }
    vis[x]=1;
}

删除同理。

查询时直接往下跳，如果 t 值未访问则说明未出现过。否则继续往下跳，跳到末尾返回 vis 值即可。

bool query(string s) {
    int x=0;
    for(int i=0; i<(int)s.size(); i++) {
        if(!t[x][get(s[i])]) return 0;
        x=t[x][get(s[i])];
    }
    return vis[x];
}

关于字典树模板，则返回 ans 值。

2.3 01-trie

插入、删除、查询同理。

重点介绍处理异或问题。

例如多次询问一个数和集合中那个数异或值最大。

尽量从高向低走和这个数相反的位置，计算答案。

3. 字典树的倒序建树

by xjd。

pushup

从低位往高位建树可以维护不同的信息，比如支持查询全局异或和，全局加一。

维护两个数组 \(v,w\)，分别表示子树异或和、子树叶节点个数的奇偶性。类似线段树，有一个用子节点更新当前节点的函数：

void pushup(int pos){
  w[pos]=v[pos]=0;
  if(tr[pos][0])w[pos]^=w[tr[pos][0]],v[pos]^=v[tr[pos][0]]<<1;
  if(tr[pos][1])w[pos]^=w[tr[pos][1]],v[pos]^=(v[tr[pos][1]]<<1)|w[tr[pos][1]];
}

对于 \(w\)，直接将子树相加即可。当前节点的 \(v\) 异或上左右子树的 \(v\)。由于从低位往高位建树，左右儿子的 \(v\) 要左移一位。当前节点往右儿子的边会产生 \(0\) 或 \(1\) 的贡献，应单独算。

那么全局异或和就是根节点的 \(v\)。

查询、删除

由于 pushup 的存在，递归会好写一点。

void insert(int a,int &pos,int d){
  if(!pos)pos=++cnt;
  if(d>maxd)w[pos]^=1;
  else insert(a>>1,tr[pos][a&1],d+1),pushup(pos);
}
void erase(int a,int pos,int d){
  if(d>maxd)w[pos]^=1;
  else erase(a>>1,tr[pos][a&1],d+1),pushup(pos);
}

全局加一

对一个数加一，二进制上会把最低位的零与更低位翻转。放到字典树上就是交换左右儿子然后沿着走零的边。

void add(int pos){
  swap(tr[pos][0],tr[pos][1]);
  if(tr[pos][0])add(tr[pos][0]);
  pushup(pos);
}

4. KMP

对于字符串 \(s\)，定义 \(\bold{Border}(s)\) 为对于 \(i \in \left [1, |s|\right)\)，满足 \(pre_i=suf_i\) 的字符串 \(pre_i\) 的集合。\(\bold{Border}(s)\) 中的每个元素都称之为字符串 \(s\) 的 \(\operatorname{border}\)。也就是字符串的最长子串，满足它既是真前缀也是真后缀。

对于一个字符串，定义其前缀函数是一个数组 \(nxt\)，\(nxt_i\) 是前缀 \(pre_i\) 的最长 \(\operatorname{border}\) 的长度。

考虑怎么快速算 \(nxt\)。

  int j=0;
  for(int i=2; i<=m; i++) {
    while(j&&t[i]!=t[j+1]) //如果跳回第一个就不用跳了
      j=nxt[j];//匹配
    if(t[j+1]==t[i]) j++;
    nxt[i]=j;//i+1失配后应该如何跳
  }

可以理解为模式串当前位置和自己前面段匹配。

最后直接在文本串上跳即可。

void kmp() {
    for(int i=1,j=0; i<=n; i++) {
        for(; j>0&&t[j+1]!=s[i]; j=nxt[j]);
        if(t[j+1]==s[i]) j++;
        if(j==m) cout<<i-m+1<<'\n';
    }
}

复杂度分析：考虑 \(j\) 每次往前匹配，但最多加一，所以是 \(O(n+m)\)。