package main import ( "fmt" ) func main() { var n, m int var s, t string fmt.Scanf("%d %d", &n, &m) fmt.Scanf("%s\n%s", &s, &t) answer := findLevenshteinDistance(s, t) fmt.Println(answer) } func findLevenshteinDistance(s, t string) int { // a b c d e // a 0 1 2 3 4 // d 1 1 2 2 3 // b 2 1 2 3 3 var dp [1001][1001]int for i := 0; i <= len(s); i++ { dp[i][0] = i } for i := 0; i <= len(t); i++ { dp[0][i] = i } for i := 0; i < len(s); i++ { for j := 0; j < len(t); j++ { if s[i] == t[j] { dp[i+1][j+1] = dp[i][j] } else { change := dp[i][j] + 1 delete := dp[i+1][j] + 1 add := dp[i][j+1] + 1 changeOrDelete := min(change, delete) // fmt.Println("change: ", change, "delete: ", delete, "add: ", add) dp[i+1][j+1] = min(changeOrDelete, add) } } } // printLimitedTable(dp, len(s), len(t)) return dp[len(s)][len(t)] } func findLcs(s, t string) int { // a b c d e // a 1 1 1 1 1 // d 1 1 1 2 2 // b 1 2 2 2 2 var dp [1001][1001]int for i := 0; i < len(s); i++ { for j := 0; j < len(t); j++ { m := max(dp[i+1][j], dp[i][j+1]) n := dp[i][j] if s[i] == t[j] { n++ } dp[i+1][j+1] = max(m, n) } } return dp[len(s)][len(t)] } func max(a, b int) int { if a > b { return a } return b } func min(a, b int) int { if a > b { return b } return a } func printLimitedTable(dp [1001][1001]int, n, w int) { fmt.Printf(" ") for i := 0; i <= w; i++ { fmt.Printf("%d ", i) } fmt.Print("\n") for i := 0; i <= n; i++ { fmt.Printf("%d: ", i) for j := 0; j <= w; j++ { fmt.Printf("%d ", dp[i][j]) } fmt.Print("\n") } }