题解 | #公共子串计算#

package main

import (
    "fmt"
)

func LCS(s1 string, s2 string) int {
    var maxLength int
    size1, size2 := len(s1), len(s2)

    // dp[i][j]: 表示s1的前i个字符和s2的前j个字符的最长公共字串
    dp := make([][]int, size1 + 1)
    for i:=0; i<len(dp); i++ {
        dp[i] = make([]int, size2 + 1)
    }

    // 初始化

    // 动态转移方程
    for i:=1; i<=size1; i++ {
        for j:=1; j<=size2; j++ {
            if s1[i-1] == s2[j-1] {
                dp[i][j] = dp[i-1][j-1] + 1
                if dp[i][j] > maxLength {
                    maxLength = dp[i][j]
                }
            }
        }
    }

    return maxLength
}

func main() {
    var s1 string
    var s2 string

    fmt.Scan(&s1, &s2)

    fmt.Println(LCS(s1, s2))
}

// 本题输入为两个不带空格的字符串，所以采用：fmt.Scan(&s1, &s2)