题解 | #公共子串计算#

空间压缩，由于每一个dp值只有在两字符串在当前位置和前一个位置都相同时需要读取前一个位置的dp值并+1，所以可以用一维数组表示，当出现上述情况时dp[j]更新为dp[j-1]，否则当前字符相同时更新为1，不相同更新为0，边界值为i或j为0的情况，此时不能求也不用求i-1和j-1

import java.util.Scanner
fun main(args: Array<String>) {fun max(a: Int, b: Int) = Math.max(a, b)
val read = Scanner(System.`in`)
val res1 = read.nextLine()
val res2 = read.nextLine()
val dp = Array(res1.length) { 0 }
var max = 0

for (i in res2.indices) {
    for (j in res1.lastIndex downTo 0) {
        if (res1[j] == res2[i]) {
            dp[j] = if (i > 0 && j > 0 && res1[j - 1] == res2[i - 1]) dp[j - 1] + 1 else 1
            max = max(max, dp[j])
        } else dp[j] = 0
    }
}
println(max)
}