import scala.collection.mutable
class SuffixTree[T, S <: Seq[T]](ps:S) {
val inf = 666666
private class Node(pl: Int = 0, pr: Int = 0, ppar: Int = -1) {
var l = pl
var r = pr
var par = ppar
var link = -1
var next: mutable.Map[T, Int] = mutable.Map()
def len(): Int = r - l
def get(c:T): Int = if (next.contains(c)) next(c) else {next(c) = -1; next(c)}
}
private class State(pv: Int, ppos: Int) {
var v = pv
var pos = ppos
}
private var s : Seq[T] = ps
private val t: mutable.Map[Int, Node] = mutable.Map()
private var sz = 1
private var ptr = new State(0,0)
private def go(pst:State, pl:Int, pr:Int) : State = {
var st = pst
var l = pl
while (l < pr)
if (st.pos == t.getOrElseUpdate(st.v, new Node()).len()) {
st = new State(t(st.v).get(s(l)), 0)
if (st.v == -1) return st
} else {
if (s(t(st.v).l + st.pos) != s(l)) return new State(-1, -1)
if (pr - l < t(st.v).len() - st.pos) return new State(st.v, st.pos + pr - l)
l += t(st.v).len() - st.pos
st.pos = t(st.v).len()
}
st
}
private def split(st:State): Int = {
val func : (State) => Int = {
case (st1) if st1.pos == t(st1.v).len() => st.v
case (st2) if st2.pos == 0 => t(st2.v).par
case (st3) =>
val v = t(st3.v)
val id = sz
sz = sz + 1
t(id) = new Node(v.l, v.l + st.pos, v.par)
t(v.par).next(s(v.l)) = id
t(id).next(s(v.l + st.pos)) = st.v
t(st.v).par = id
t(st.v).l += st.pos
id
}
func(st)
}
private def get_link(v:Int): Int = {
val func : (Int) => Int = {
case (v1) if t(v1).link != -1 => t(v1).link
case (v2) if t(v2).par == -1 => 0
case (v3) =>
val to = get_link(t(v3).par)
val e = if (t(v3).par==0) 1 else 0
val lst = new State(to,t(to).len())
t(v3).link = split (go(lst, t(v3).l+e, t(v).r))
t(v3).link
}
func(v)
}
private def tree_extend(pos:Int): Unit = {
var cond = true
while(cond) {
val nptr = go (ptr, pos, pos+1)
if (nptr.v != -1) {
ptr = nptr
return
}
val mid = split (ptr)
val leaf = sz
sz = sz + 1
t(leaf) = new Node (pos, inf, mid)
t(mid).next(s(pos)) = leaf
ptr.v = get_link (mid)
ptr.pos = t(ptr.v).len()
if (mid==0) cond=false
}
}
def exist(f:S): Boolean = {
var st = new State(0,0)
val r = f.length
var l = 0
while (l < r)
if (st.pos == t(st.v).len()) {
st = new State(t(st.v).get(f(l)),0)
if (st.v == -1) return false
} else {
if (s(t(st.v).l + st.pos) != f(l)) return false
l+=1
st.pos+=1
}
true
}
def find(f:S): Int = {
var st = new State(0,0)
var index = 0
val r = f.length
var l = 0
while (l < r)
if (st.pos == t(st.v).len()) {
val pr = t(st.v).r
st = new State(t(st.v).get(f(l)),0)
if (st.v == -1) return -1
index += t(st.v).l - pr
} else {
if (s(t(st.v).l + st.pos) != f(l)) return -1
l += 1
st.pos += 1
}
index
}
private var i = 0
while (i<s.length) {
tree_extend(i)
i = i + 1
}
def add(f:S): Unit = {
s = s ++ f
while (i<s.length) {
tree_extend(i)
i = i + 1
}
}
}