package main

import (
	"fmt"
)

func longestCommonSubsequence(text1 string, text2 string) int {
	n1 , n2 := len(text1) , len(text2)
	if n1 > n2 {
		text1 , text2 , n1 , n2  = text2 , text1 , n2 ,n1
	}
	text2 , n2 = "1" +text2 , n2 + 1
	dp := make([][]int,n1,n1)
	for i := range dp {
		dp[i] = make([]int,n2,n2)
	}
	for j := 1 ; j < n2 ; j ++{
		if text2[j] == text1[0] {
			for ; j < n2 ; j++{
				dp[0][j] = 1
			}
		}
	}
	for i := 1 ; i < n1 ; i++ {
		for j := 1 ; j < n2 ; j++ {
			dp[i][j] = max(dp[i-1][j],dp[i][j-1])
			if text1[i] == text2[j]  && dp[i-1][j-1] != 0{
				dp[i][j] ++
			}
		}
	}
	return dp[n1-1][n2-1]
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	fmt.Println(longestCommonSubsequence("ubmrapg","ezupkr"))
}