后缀自动机

介绍 首先后缀自动机 可以包括给定字符串的所有子串 O(n) 是自动机 一些定义 endpos 字符串s的一个子串t，endpos(t)为s中t的所有结束位置构成的集合 SAM是一个最小的DFA 有向无环图 节点是状态，边是转移 转移是一些字母 从源点出发到终止状态所有转移连起来的字 ...
2021-11-20 00算法 > 字符串