package sprint8.fin.B

fun main() {
    val a = Trie("abaab")
}

class Trie(inputString: String) {
    private val terminator = '$'
    val string = "$inputString$terminator"
    val root: Node = Node().apply { addVertex(Vertex(string.lastIndex, string.length)) }

    inner class Node(inputVertex: Vertex?) {
        constructor() : this(null)

        val stringUntil = inputVertex?.right ?: 0

        private val vertices = mutableMapOf<Char, Vertex>()

        fun addVertex(vertex: Vertex) {
            vertices[vertex.startChar] = vertex
        }

        fun hasVertex(char: Char) = vertices.containsKey(char)

        fun getVertex(char: Char) = vertices[char]

        operator fun get(char: Char) = vertices[char]

        val sufLink: Position
            get() {
                var cur = root
                var curPos = 1
                while (curPos < stringUntil) {
                    val vertex = cur.vertices[string[curPos]]!!
                    cur = vertex.to
                    curPos += vertex.len
                }
                return cur.position
            }

        val position = Position(this)

        override fun toString(): String = string.substring(0, stringUntil)
    }

    inner class Vertex(val left: Int, right: Int) {
        constructor(left: Int) : this(left, string.length)

        var right = right
            private set
        var to = Node(this)
        val startChar = string[left]

        val len
            get() = right - left

        fun split(pos: Int): Node {
            val splitOffVertex = Vertex(left + pos, right).also { it.to = this.to }
            right = splitOffVertex.left

            return Node(this)
                .also {
                    to = it
                    it.addVertex(splitOffVertex)
                }
        }

        override fun toString(): String {
            return string.substring(left, right)
        }
    }

    inner class Position(val node: Node, val char: Char?, val pos: Int) {
        constructor(node: Node) : this(node, null, 0)

        val isNode get() = pos == 0

        val link: Position
            get() {
                if (char == null || pos == 0) return node.sufLink
                var node = node.sufLink.node
                var pos = this.pos
                var char = this.char
                var vertex = node[char]!!
                while (pos > vertex.len) {
                    node = vertex.to
                    pos -= vertex.len
                    char = string[node.stringUntil]
                    vertex = node[char]!!
                }
                return Position(node, char, pos)
            }

        override fun toString(): String = "${node}${string.substring(node.stringUntil, pos)}"
    }

    init {
        var curr = root.position
        fun add(addPos: Int) {
            val char = string[addPos]
            while (curr.node != root && !curr.node.hasVertex(char)) {
                if (!curr.isNode) {
                    curr.node.getVertex(char)
                        ?.split(curr.pos)
                        ?.addVertex(Vertex(addPos, string.length))
                    curr = curr.link
                }
            }
            if (curr.isNode && curr.node.hasVertex(char) || string[curr.node.stringUntil + curr.pos] == char) {
                curr = Position(curr.node, curr.char, curr.pos + 1)
            } else {
                curr.node.addVertex(Vertex(addPos))
            }
        }

        for (i in string.indices) {
            add(i)
        }
    }
}