suffix-preffix.scala

object Solution extends App {

  val bf = Array.newBuilder[String]

  (1 to Console.readLine().toInt)
    .map(_ => Console.readLine())
    .foreach(s => println(calc(s)))

  @annotation.tailrec 
  def sum(n: Int, res: Int = 0): Int = if (n <= 0) res else sum(n - 1, res + n)

  def calc(s: String): Int = {
    if (s.toSet.size == 1) return sum(s.size)

    bf.clear()
    val f = s(0)

    s.foldLeft(0) { (i, c) =>
      if (i > 0 && c == f) bf += s.substring(i)
      i + 1
    }

    cnt(s, bf.result(), 0, s.size)
  }

  @annotation.tailrec
  def cnt(s: String, sf: Array[String], n: Int, res: Int): Int = 
    sf.filter(c => c.size > n && c(n) == s(n)) match {
      case e if e.isEmpty => res
      case tail => cnt(s, tail, n + 1, res + tail.size)
    }
}