题解 | 最长公共子串

package main

import (
    "fmt"
)

func main() {
    var str1 string
    var str2 string
    for {
        n, _ := fmt.Scan(&str1, &str2)
        if n == 0 {
            break
        } else {
            str := process(str1, str2)
            if len(str) > 0 {
                fmt.Println(str)
            } else {
                fmt.Println(-1)
            }
        }
    }
}
// o（1）复杂度带分析
// 空间复杂度为 o（n） 时间复杂度为 o（n*m）
func process(str1 string, str2 string) string {
    dp := make([]int, len(str2)+1)
    maxi, maxl := 0, 0
    for i:=1; i<len(str1)+1; i++ {
        for j:=len(dp)-1; j>=1; j-- {
            if str1[i-1] == str2[j-1] {
                dp[j] = dp[j-1]+1
                if dp[j] > maxl {
                    maxl = dp[j]
                    maxi = i
                } 
            } else {
                dp[j] = 0 // 需要复原为0
            }
        }
    }
    if maxl > 0 {
        return str1[maxi-maxl:maxi]
    } 
    return ""
}
// 空间复杂度为 o（n*m） 时间复杂度为 o（n*m）
// func process(str1 string, str2 string) string {
//     dp := make([][]int, len(str1)+1)
//     for i:=0; i<len(dp); i++ {
//         dp[i] = make([]int, len(str2)+1)
//     }
//     maxi, maxl := 0, 0
//     for i:=1; i<len(dp); i++ {
//         for j:=1; j<len(dp[i]); j++ {
//             if str1[i-1] == str2[j-1] {
//                 dp[i][j] = dp[i-1][j-1]+1
//                 if dp[i][j] > maxl {
//                     maxl = dp[i][j]
//                     maxi = i
//                 }
//             }
//         }
//     }
//     if maxl > 0 {
//         return str1[maxi-maxl:maxi]
//     } 
//     return ""
// }