题解 | #公共子串计算#
公共子串计算
http://www.nowcoder.com/practice/98dc82c094e043ccb7e0570e5342dd1b
package main import ( "fmt" "bufio" "os"
)
func main() { input := bufio.NewScanner(os.Stdin) input.Scan() s := input.Text() input.Scan() t := input.Text() result := publicSubstring(s, t) fmt.Println(result) }
func publicSubstring(s, t string) int { dp := make([][]int, len(s)+1) for i := 0; i < len(s)+1; i++ { dp[i] = make([]int, len(t)+1) } result := 0 for i := 1; i <= len(s); i++ { for j := 1; j <= len(t); j++ { if s[i-1]==t[j-1] { dp[i][j] = dp[i-1][j-1]+1 } if dp[i][j] > result { result = dp[i][j] } } } return result }