TypewriterMonkey.scala

import java.io.FileOutputStream
import scala.io.Source

object TypewriterMonkey {
  val INPUT = "B-large-practice.in"
  val OUTPUT = INPUT.takeWhile(_ != '.') + ".out"
  val isConsole = false

  def main(args: Array[String]): Unit = {
    val itr = Source.fromFile(INPUT).getLines()
    val stream = if (isConsole) Console.out else new FileOutputStream(OUTPUT)
    try {
      Console.withOut(stream) {
        val sets = itr.next().toInt
        (1 to sets).foreach { set =>
          val length = itr.next().split(' ').last.toInt
          val keys = itr.next()
          val target = itr.next()
          println(f"Case #$set: ${numberOfBananas(keys, length, target)}")
        }
      }
    } finally {
      stream.flush()
      if (!isConsole) stream.close()
    }
  }

  def bringBananas(length:Int, target:String):Int = {
    def makePerfect(accr:Int):Int = accr match {
      case _ if target.length == accr => target.length
      case _ if target.drop(accr) == target.take(target.length - accr) => accr
      case _ => makePerfect(accr + 1)
    }
    val `겹치는갯수` = target.length - makePerfect(1)
    val `안겹치는갯수` = target.length - `겹치는갯수`
    (length - `겹치는갯수`)/`안겹치는갯수`
  }

  def keyboardMap(keys:String):Map[Char, Double] = {
    val total = keys.length
    keys.groupBy(x => x).mapValues(_.length.toDouble / total)
  }

  def numberOfBananas(keys:String, length:Int, target:String):Double = {
    if(!(target.toSet.equals(keys.toSet & target.toSet))) 0.0
    else {
      val bananas = bringBananas(length, target)
      val map = keyboardMap(keys)
      val probability = (1.0 /: target){
        case (p, key) => p * map(key)
      }
      //(length - target.length + 1)
      bananas - probability * (length - target.length + 1)
    }
  }
}