Advertisement
paranid5

NOP

Feb 9th, 2021
354
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Kotlin 1.26 KB | None | 0 0
  1. fun main() {
  2.     val read = {
  3.         readLine()!!.toInt() to readLine()!!.split(' ').map { it.toInt() }.toIntArray()
  4.     }
  5.  
  6.     val (n, fst) = read()
  7.     val (m, sec) = read()
  8.  
  9.     MutableList(n + 1) { MutableList(m + 1) { 0 } }
  10.         .also {
  11.             (1..n).forEach { i ->
  12.                 (1..m).forEach { q ->
  13.                     when {
  14.                         fst[i - 1] == sec[q - 1] -> it[i][q] = it[i - 1][q - 1] + 1
  15.                         else -> it[i][q] = maxOf(it[i - 1][q], it[i][q - 1])
  16.                     }
  17.                 }
  18.             }
  19.         }
  20.         .also { println(it[n][m]) }
  21.         .let {
  22.             mutableListOf<Int>()
  23.                 .also { ans ->
  24.                     var i = n
  25.                     var q = m
  26.  
  27.                     while (i > 0 && q > 0) {
  28.                         when {
  29.                             fst[i - 1] == sec[q - 1] -> {
  30.                                 ans.add(fst[i - 1])
  31.                                 i--; q--
  32.                             }
  33.                             it[i - 1][q] == it[i][q] -> i--
  34.                             else -> q--
  35.                         }
  36.                     }
  37.                 }
  38.                 .let { ans -> ans.asReversed().forEach { print("$it ") } }
  39.         }
  40. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement