package cap4

import "strings"

// Ex27 最长公共子序列
func Ex27(str1, str2 []rune) (int, string) {
	dp := _makeMatrix(len(str1)+1, len(str2)+1)
	subStr := strings.Builder{}
	for i := 1; i <= len(str1); i++ {
		for j := 1; j <= len(str2); j++ {
			a, b := str1[i], str2[j]
			if a == b {
				dp[i][j] = dp[i-1][j-1] + 1
				subStr.WriteRune(a)
			} else {
				dp[i][j] = max(dp[i-1][j], dp[i][j-1])
			}
		}
	}

	return dp[len(str1)][len(str2)], subStr.String()
}