最简单的字符串

随便投稿一篇关于简单字符串的文章

内容包含:Hash, Trie, KMP, AC Automaton

1 HASH

用处

字符串判断相等

算法思想

把字符串用一个$n$位$p$进制数的形式表现出,因为C++判数的大小是O(1)的所以可以随便判断

算法步骤

1 每个字符代表着一个$p$进制的一位数(一般取$p=131$,代表的数一般为字符串本身的 ASCII 数值)

2 预计算出字符串的前缀/后缀代表的数字,如下
(注意,pre 和 suf 要开 ull)

3 对于需要的问询,利用前缀和或后缀和计算就可以了

2 TRIE

用处:

多串前后缀匹配

算法思想:

用树代表着n个字符串,LCP即这棵树的根到LCA

算法步骤:

1 建一棵26分树,边代表字符,那么从根到达一个节点链上的字符串就是一个前缀

但显然节点个数太多了,于是可以用动态开点优化

2 插入:沿着树边向下走,走到终结节点就重数+1

3 查询以前缀t为前缀的数量:要记录前缀重数和

3 KMP

用处:

单模式串匹配
假设文本串长度为$n$, 模式串长度为$m$

暴力:

对于文本串的每一位,看向后$m$位是否匹配原模式串

可用 hash 优化(kmp:这是我的主场好不好)

优化分析:

浪费在每次看向后$m$位是否匹配原模式串,之前的比较信息全都浪费了

于是我们希望每次匹配时之前的信息还可以用

算法思想:

匹配$(i,j)$的意思是文本串的子串$(i,i-j+1)$可以匹配上模式串的前缀子串$(1,j)$

  • 对于匹配$(i,j)$且pattern[j+1]==text[i+1],那么增量式即可

  • 对于匹配$(i,j)$但patter[j+1]!=text[i+1],那么我们需要找到最大的$j'<j$使得匹配$(i,j')$成立,然后再向后增量式

    因为这样就可以利用知道的文本串的子串$(i,i-j'-1)$和模式串的子串$(1,j')$是匹配的 '

    而且,我们还可以预计算$j'$

    我们把j'叫做j的失败指针,即next[j]

算法步骤

遍历文本串的每一位text[i]

然后判断如果text[i+1]==pattern[j+1], 那么就j++

如果不是,那么取j=next[j]直到text[i+1]==pattern[j+1]为止

如果$j$已经变成了$0$,即找不到任意匹配,那么只能移动$i$让$i$去匹配$j$(程序里就是$j$不发生变化等待$i$变成可匹配的值)

判断是否完成匹配:j==m
如果需要求出有多少个匹配,那么重新回到j=next[j]做新的匹配

然后是预计算nxt[j]

算法思想:

nxt[j]的含义是找到最大的$j'$使得匹配$(i,j)$成立然后$(i,j')$成立。

看到上面一张图,蓝色为匹配成功的,绿色为patter[j+1]!=text[i+1]

我们很快的发现最大的$j'=6$,那么有什么性质呢?

pattern 的子串$(1,j')$必须和 text 的子串$(i-j'+1,i)$一样,
而 text 的子串$(i-j'+1,i)$又是前一个匹配的 pattern 的子串$(j-j'+1,j)$, 那么意味着:
pattern 的两个子串$(1,j')$和$(j-j'+1,j)$是相同的

那么就意味着,子串$(1,j)$的长度为$j'$的前缀和后缀是相同的,那么求nxt[j]就是求最长相同前后缀长度

那么就是要求,pattern 的前后缀匹配,就是 pattern 自己的一个自身匹配

算法步骤:

$i$遍历模式串的后缀最后一个字符
$j$遍历模式串的前缀最后一个字符

如果 pattern[i+1]==pattern[j+1]增量式求解,意味着nxt[i+1]=j+1

如果不是,取j=nxt[j],直到相等或$j$变成了$0$

nxt[j]=0表示这个无法前后缀匹配

因为$j$ 给你一个字符串,它是由某个字符串不断自我连接形成的一个字符串的子串。 但是这个字符串是不确定的,现在只想知道它的最短长度是多少。

若一个前缀和后缀匹配,那么去除这个前缀的子串一定是一个循环节

那么找出最短的循环节,就是最长的前后缀匹配即可

4 AC自动机

用处:

多模式串匹配

分析:

既然是多模式串匹配,那么为了更好的利用前缀这一特性,我们可以把 KMP 搬到 Trie 树上

算法思想:

与文本串匹配时同KMP

模式串之间的匹配用Trie:
假设我们已经有假设$u$是$v$在 Trie 树上的儿子

利用 Trie 的前缀特性(姑且称之为此吧),可以很快的找到一个匹配

算法步骤:

假设我们已经得到了一个匹配$u$和$\operatorname{nxt}_u$,那么我们现在要求出$v$的$\operatorname{nxt}_v$

和KMP一样,我们先看$\operatorname{nxt}_u$是否有一个字符和这个相等的儿子,如果有,那么直接增量式求解

如果没有,我们先设$p$为现在的nxt指向的,那么为了保证前面的还能匹配上,我们把$p$变为$\operatorname{nxt}_p$,原理同KMP,继续匹配

注意:TRIE树上ch[0][k]=1,这样才能保证可以向后进行匹配

计算顺序:因为$d_u>d_{nxt}$,所以用BFS顺序计算

对于那个路径压缩,对于这个不存在的点ch[u][i],需要找的点就是nxt[ch[nxt][i]],做一下路径压缩节省时间

发表评论