import scala collection immutable TreeMap class SuffixTree var current

  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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
import scala.collection.immutable.TreeMap
class SuffixTree() {
var currentStringCounter = 0
var cur_id = 0
var linkMap = new TreeMap[Int, Vertex]
var root = new Vertex(null, 0, 0, null, cur_id)
linkMap += (cur_id -> root)
var last : Vertex = null
var maskAllStringsPassed = 0
var LongestCommonPath : Vertex = root
def addSuffixToVertex(begin: Vertex, newString: String, start: Int): Vertex = {
val passedStringMask = 1 << currentStringCounter
begin.passedStringsMask |= passedStringMask
var currentVertex = begin
var currentChar = newString.charAt(start)
var i = start
if (currentVertex.children.contains(currentChar)) {
currentVertex = currentVertex.children apply currentChar
var j = currentVertex.startIndex
while (true) {
if (j == currentVertex.endIndex + 1) {
currentVertex.passedStringsMask |= passedStringMask
return addSuffixToVertex(currentVertex, newString, i)
} else {
var newStringCurChar = newString.charAt(i)
var treeStringCurChar = currentVertex.workString.charAt(j)
if (newStringCurChar != treeStringCurChar) {
cur_id += 1
var newVertex = new Vertex(currentVertex.workString, currentVertex.startIndex, j - 1, currentVertex.parent, cur_id)
linkMap += (cur_id -> newVertex)
currentVertex.parent.children += (currentChar -> newVertex)
currentVertex.startIndex = j
currentVertex.parent = newVertex
newVertex.children += (treeStringCurChar -> currentVertex)
newVertex.passedStringsMask = currentVertex.passedStringsMask
newVertex.pathLength = newVertex.parent.pathLength + newVertex.workStringLength() + 1
newVertex.passedStringsMask |= passedStringMask
return addSuffixToVertex(newVertex, newString, i)
}
}
i += 1
j += 1
}
}
cur_id += 1
var newVertex = new Vertex(newString, start, newString.length() - 1, begin, cur_id)
linkMap += (cur_id -> newVertex)
begin.children += (currentChar -> newVertex)
newVertex.pathLength = begin.pathLength + newVertex.workStringLength() + 1
newVertex.passedStringsMask |= passedStringMask
return newVertex
}
def SearchPosition(begin_id: Int, SearchStr: String, start: Int, end: Int): Vertex = {
var begin = linkMap(begin_id)
var passedStringMask = 1 << currentStringCounter
begin.passedStringsMask |= passedStringMask
if (start > end) {
return begin
}
var currentVertex = begin.children apply SearchStr.charAt(start)
if ((end - start) >= currentVertex.workStringLength()) {
currentVertex.passedStringsMask |= passedStringMask
return SearchPosition(currentVertex.id, SearchStr, start + currentVertex.workStringLength() + 1, end)
} else {
var currentChar = SearchStr.charAt(start)
cur_id += 1
var newVertex = new Vertex(currentVertex.workString, currentVertex.startIndex, currentVertex.startIndex + (end - start), begin, cur_id)
linkMap += (cur_id -> newVertex)
begin.children += (currentChar -> newVertex)
currentVertex.startIndex = currentVertex.startIndex + end - start + 1
currentVertex.parent = newVertex
newVertex.passedStringsMask = currentVertex.passedStringsMask
newVertex.children += (currentVertex.workString.charAt(currentVertex.startIndex) -> currentVertex)
newVertex.pathLength = begin.pathLength + newVertex.workStringLength() + 1
newVertex.passedStringsMask |= passedStringMask
return newVertex
}
}
def addSuffix(newString: String, start: Int) = {
if (last.parent == root) {
var newVertex = addSuffixToVertex(root, newString, start)
last = newVertex
} else if (last.parent.parent == root) {
var oldLastParent = last.parent
var foundPosition = SearchPosition(root.id, last.parent.workString, last.parent.startIndex + 1, last.parent.endIndex)
var newVertex = addSuffixToVertex(foundPosition, last.workString, last.startIndex)
oldLastParent.suffixLink = foundPosition.id
last = newVertex
} else {
var oldLastParent = last.parent
var foundPosition = SearchPosition(last.parent.parent.suffixLink, last.parent.workString, last.parent.startIndex, last.parent.endIndex)
var newVertex = addSuffixToVertex(foundPosition, last.workString, last.startIndex)
oldLastParent.suffixLink = foundPosition.id
last = newVertex
}
}
def addString(newString: String) = {
var passedStringMask = 1 << currentStringCounter
root.passedStringsMask |= passedStringMask
if (currentStringCounter == 0) {
cur_id += 1
var newVertex = new Vertex(newString, 0, newString.length()-1, root, cur_id)
linkMap += (cur_id -> newVertex)
root.children += (newString.charAt(0) -> newVertex)
last = newVertex
newVertex.pathLength = newVertex.workStringLength() + 1
newVertex.passedStringsMask |= passedStringMask
} else {
last = addSuffixToVertex(root, newString, 0)
}
var i = 1
for (i <- 1 until newString.length()) {
this addSuffix(newString, i)
}
currentStringCounter += 1
}
def findLCP(vertex: Vertex = root) {
if ((vertex.passedStringsMask == maskAllStringsPassed) && (vertex.pathLength > LongestCommonPath.pathLength)) {
LongestCommonPath = vertex
}
if (vertex.children != null) {
vertex.children foreach{ case (k, v) => findLCP(v)}
}
}
def printLCP() {
def getLCPRec(v: Vertex, list: List[String]):List[String] = v match {
case vertex if vertex == root => list
case _ => {
val partOfLCPString = v.workString.substring(v.startIndex, v.endIndex + 1)
getLCPRec(v.parent, partOfLCPString :: list)
}
}
var pathNameList = getLCPRec(LongestCommonPath, Nil)
print(pathNameList)
}
}