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

package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {

	s := bufio.NewScanner(os.Stdin)

	for s.Scan() {
		pre := s.Text()
		s.Scan()
		suf := s.Text()
		check([]rune(pre), []rune(suf))
	}

}

func check(pre []rune, suf []rune) {
	maxCount := 0
	maxIndex := 0
	if len(pre) > len(suf) {
		suf, pre = pre, suf
	}

	dp := make([][]int, len(pre))
	for i := range dp {
		dp[i] = make([]int, len(suf))
	}

	for i, r1 := range pre {
		if r1 == suf[0] {
			dp[i][0] = 1
		}
	}

	for j, r2 := range suf {
		if r2 == pre[0] {
			dp[0][j] = 1
		}
	}

	for i := 1; i < len(pre); i++ {
		for j := 1; j < len(suf); j++ {
			if pre[i] == suf[j] {
				dp[i][j] = dp[i-1][j-1] + 1
			}
			if dp[i][j] > maxCount {
				maxCount = dp[i][j]
				maxIndex = i
			}
		}
	}
	fmt.Println(string(pre[maxIndex-maxCount+1 : maxIndex+1]))
}