题解 | #查找两个字符串a,b中的最长公共子串#

package main

import (
    "fmt"
)

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func LCS(s1 string, s2 string) string {
    // 选取最短的为 s1
    if len(s1) > len(s2) {
        s1, s2 = s2, s1
    }

    var longest int
    var idx int
    len1, len2 := len(s1), len(s2)

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

    // 初始化

    // 动态转移方程
    for i:=1; i<=len1; i++ {
        for j:=1; j<=len2; j++ {
            if s1[i-1] == s2[j-1] {
                dp[i][j] = dp[i-1][j-1]+1
                if dp[i][j] > longest {
                    // fmt.Printf("i:%d,j:%d,longest:%d\n", i, j, longest)
                    longest = dp[i][j]
                    idx = i
                }
            }
        }
    }
    
    // 找到最长的公共字串
    return s1[idx-longest:idx]
}

func main() {
    var s1 string
    var s2 string

    fmt.Scan(&s1, &s2)

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

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