import scala.collection.mutable.Stack
class SuffixTree {
var currentStringCounter : Int
var root : Vertex
var last : Vertex
var LongestCommonPath : Vertex
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.get(currentChar)) {
currentVertex = currentVertex.children.get(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) {
var newVertex = new Vertex(currentVertex.workString, currentVertex.startIndex, j - 1, currentVertex.parent)
currentVertex.parent.children.put(currentChar, newVertex)
currentVertex.startIndex = j
currentVertex.parent = newVertex
newVertex.children.put(treeStringCurrentChar, currentVertex)
newVertex.passedStringsMask = currentVertex.passedStringsMask
newVertex.pathLength = newVertex.parent.pathLength + newVertex.workStringLength() + 1
newVertex.passedStringsMask |= passedStringMask
return AddSuffixToVertex(newVertex, newString, i)
}
}
i++; j++
}
} else {
var newVertex = new Vertex(newString, start, newString.length() - 1, begin)
begin.children.put(currentChar, newVertex)
newVertex.pathLength = begin.pathLength + newVertex.workStringLength() + 1
newVertex.passedStringsMask |= passedStringMask
return newVertex
}
}
def SearchPosition(begin: Vertex, SearchStr: String, start: Int, end: Int): Vertex = {
var passedStringMask = 1 << currentStringCounter
begin.passedStringsMask |= passedStringMask
if (start > end) {
return begin
}
var currentVertex = begin.children.get(SearchStr.charAt(start))
if ((end - start) >= currentVertex.workStringLength()) {
currentVertex.passedStringsMask |= passedStringMask
return SearchPosition(currentVertex, SearchStr, start + currentVertex.workStringLength() + 1, end)
} else {
char currentChar = SearchStr.charAt(start)
var newVertex = new Vertex(currentVertex.workString, currentVertex.startIndex, currentVertex.startIndex + (end - start), begin)
begin.children.put(currentChar, newVertex)
currentVertex.startIndex = currentVertex.startIndex + end - start + 1
currentVertex.parent = newVertex
newVertex.passedStringsMask = currentVertex.passedStringsMask
newVertex.children.put(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, last.parent.workString, last.parent.startIndex + 1, last.parent.endIndex)
var newVertex = AddSuffixToVertex(foundPosition, last.workString, last.startIndex)
oldLastParent.suffixLink = foundPosition
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
last = newVertex
}
}
def AddString(newString: String) = {
if (root == null) {
root = new Vertex(null, 0, 0, null)
}
int passedStringMask = 1 << currentStringCounter
root.passedStringsMask |= passedStringMask
if (currentStringCounter == 0) {
var newVertex = new Vertex(newString, 0, newString.length()-1, root)
root.children.put(newString.charAt(0), newVertex)
last = newVertex
newVertex.pathLength = newVertex.workStringLength() + 1
newVertex.passedStringsMask |= passedStringMask
} else {
last = AddSuffixToVertex(root, newString, 0)
}
// Debug: print the SuffixTree
//TraverseAndPrint(this);
var i = 0
for (i <- 0 until newString.length()) {
this AddSuffix(newString, i)
// Debug: print the SuffixTree
//TraverseAndPrint(this);
}
currentStringCounter++
}
def FindLongestCommonPath() = {
LongestCommonPath = root
FindLongestCommonPathRecursive(root)
}
def FindLongestCommonPathRecursive(currentVertex: Vertex) {
if ((currentVertex.passedStringsMask == maskAllStringsPassed) && (currentVertex.pathLength > LongestCommonPath.pathLength)) {
LongestCommonPath = currentVertex
}
if (currentVertex.children != null) {
var id: Char = 0
for (id <- currentVertex.children.keySet()) {
FindLongestCommonPathRecursive(currentVertex.children.get(id))
}
} else {
return
}
}
def printLongestCommonPath() {
var pathStack: Stack[String] = new Stack[String]
var currentVertex: Vertex = null
for (currentVertex = LongestCommonPath; currentVertex != root; currentVertex = currentVertex.parent) {
pathStack.push(currentVertex.workString.substring(currentVertex.startIndex, currentVertex.endIndex + 1));
}
while (!pathStack.isEmpty()) {
System.out.print(pathStack.pop());
}
System.out.println();
}
}