KMP 알고리즘 with Kotlin

 

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.*
 
 
val br = BufferedReader(InputStreamReader(System.`in`))
val bw = BufferedWriter(OutputStreamWriter(System.out))
 
fun main()=with(br){
    val parent = "ababacabacaabacaaba"
    val pattern = "abacaaba"
    KMP(parent, pattern)
    bw.flush()
    bw.close()
}
 
fun makeTable(pattern:String):IntArray{
    val patternSize = pattern.length
    val table = IntArray(patternSize){0}
    var j = 0
    for(i in 1 until patternSize){
        while(j>0 && pattern[i]!=pattern[j]){
            j=table[j-1]
        }
        if(pattern[i]==pattern[j]){
            table[i]=++j
        }
    }
    return table
}
 
fun KMP(parent:String, pattern:String){
    val table = makeTable(pattern)
    val parentSize = parent.length
    val patternSize = pattern.length
    var j = 0
    for(i in 0 until parentSize){
        while(j>0 && parent[i]!=pattern[j]){
            j=table[j-1]
        }
        if(parent[i]==pattern[j]){
            if(j==patternSize-1){
                println("${i-patternSize+2}에서 찾았습니다.")
                j=table[j]
            }
            else{
                j++
            }
        }
    }
}