blob: 20b1bc097d347b2836287d56cb82b76a954a9117 (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
package main
import "fmt"
func max(a, b int) int {
if a > b {
return a
}
return b
}
func longestCommonSubsequence(text1 string, text2 string) int {
l1 := len(text1)
l2 := len(text2)
dp := make([][]int, l1+1)
for i := range dp {
dp[i] = make([]int, l2+1)
}
for i := 0; i < l1; i++ {
for j := 0; j < l2; j++ {
if text1[i] == text2[j] {
dp[i+1][j+1] = dp[i][j] + 1
} else {
dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
}
}
}
return dp[l1][l2]
}
func main() {
fmt.Println(longestCommonSubsequence("abcde", "ace"))
fmt.Println(longestCommonSubsequence("abc", "abc"))
fmt.Println(longestCommonSubsequence("abc", "def"))
fmt.Println(longestCommonSubsequence("aced", "aceaced"))
}
|
