LongestCommonSubsequence function
(a string, b string)
| 14 | |
| 15 | // LongestCommonSubsequence function |
| 16 | func LongestCommonSubsequence(a string, b string) int { |
| 17 | aRunes, aLen := strToRuneSlice(a) |
| 18 | bRunes, bLen := strToRuneSlice(b) |
| 19 | |
| 20 | // here we are making a 2d slice of size (aLen+1)*(bLen+1) |
| 21 | lcs := make([][]int, aLen+1) |
| 22 | for i := 0; i <= aLen; i++ { |
| 23 | lcs[i] = make([]int, bLen+1) |
| 24 | } |
| 25 | |
| 26 | // block that implements LCS |
| 27 | for i := 0; i <= aLen; i++ { |
| 28 | for j := 0; j <= bLen; j++ { |
| 29 | if i == 0 || j == 0 { |
| 30 | lcs[i][j] = 0 |
| 31 | } else if aRunes[i-1] == bRunes[j-1] { |
| 32 | lcs[i][j] = lcs[i-1][j-1] + 1 |
| 33 | } else { |
| 34 | lcs[i][j] = Max(lcs[i-1][j], lcs[i][j-1]) |
| 35 | } |
| 36 | } |
| 37 | } |
| 38 | // returning the length of longest common subsequence |
| 39 | return lcs[aLen][bLen] |
| 40 | } |