import scala collection mutable class SuffixTree Seq ps val inf 666666

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
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
}
}
}