SuffixAutomaton.js

/*
  参考：
  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