Skip to content

Instantly share code, notes, and snippets.

@zhanhongtao
Created May 2, 2020 02:08
Show Gist options
  • Save zhanhongtao/6b3418cb82b32ea65c0a14b4be9c780b to your computer and use it in GitHub Desktop.
Save zhanhongtao/6b3418cb82b32ea65c0a14b4be9c780b to your computer and use it in GitHub Desktop.
/*
参考:
https://saisumit.wordpress.com/2016/01/26/suffix-automaton/
https://ksmeow.moe/suffix_automaton/
https://www.cnblogs.com/meowww/p/6394960.html
https://codeforces.com/blog/entry/20861
https://yeah.moe/p/a8e74947/
*/
// prefix
// suffix
function create(char = '') {
return {
char,
link: null,
edges: {},
length: 0,
last: false,
}
}
function SuffixAutomaton(s) {
let nodes = []
// 初始化 i 节点
let start = create('')
nodes.push(start)
start.length = 0
// 上一次处理的节点
let last = start
// 可 online 算法实现
for (let i = 0; i < s.length; ++i) {
let char = s[i]
let node = create(char)
nodes.push(node)
node.length = i + 1
node.link = start
// 向前走
let p = last
while(p && p.edges[char] == null) {
p.edges[char] = node
p = p.link
}
// 遇到重复字符
if (p) {
let q = p.edges[char]
// 0. 已存在
if (p.length + 1 === q.length) {
node.link = q
} else {
// 1. 复制
let duple = create(q.char)
nodes.push(duple)
duple.edges = { ...q.edges }
duple.link = q.link
duple.length = p.length + 1
// 2. 调整俩链接
node.link = duple
q.link = duple
// 3. 向回更新
while(p && p.edges[q.char] == q) {
p.edges[q.char] = duple
p = p.link
}
}
}
last = node
}
// 根据 last 向回更新 last 属性
while(last) {
last.last = true
last = last.link
}
return start
}
exports.auto = SuffixAutomaton
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment