2020-2021:teams:too_low:后缀自动机
|
2020-2021:teams:too_low:后缀自动机 [2020/06/19 10:19] dragonylee 创建 |
2020-2021:teams:too_low:后缀自动机 [2020/06/19 10:21] (当前版本) dragonylee |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | === 后缀自动机 === | + | ===== 后缀自动机 ===== |
| 后缀自动机（suffix-automaton, SAM）用一种高压缩的方式存储了文本串的所有子串信息，其中最重要的信息是**状态结点**，**转移**和**后缀连接**。下图表示字符串''%%banana%%''的后缀自动机，其中红色虚线代表后缀连接。 | 后缀自动机（suffix-automaton, SAM）用一种高压缩的方式存储了文本串的所有子串信息，其中最重要的信息是**状态结点**，**转移**和**后缀连接**。下图表示字符串''%%banana%%''的后缀自动机，其中红色虚线代表后缀连接。 | ||
| 行 98: | 行 98: | ||
| <html><br/></html><html><br/></html><html><br/></html> | <html><br/></html><html><br/></html><html><br/></html> | ||
| - | === 广义后缀自动机 === | + | ===== 广义后缀自动机 ===== |
| 就是可以处理多个字符串后缀信息的后缀自动机，据说是一种Trie+SAM的结构，但是以下的做法一般来说也没什么问题： | 就是可以处理多个字符串后缀信息的后缀自动机，据说是一种Trie+SAM的结构，但是以下的做法一般来说也没什么问题： | ||
2020-2021/teams/too_low/后缀自动机.1592533145.txt.gz · 最后更改: 2020/06/19 10:19 由 dragonylee
