Finds the longest common subsequence of l1 and l2. Returns a list of common parts and a list of differences. >>> lcs([1, 2, 3], [2]) ([2], [1, 3]) >>> lcs([1, 2, 3, 3, 4], [2, 3, 4, 5]) ([2, 3, 4], [1, 3, 5]) >>> lcs('banana', 'baraban') (['b', 'a', 'a', 'n'], ['a', 'r',
(l1, l2, eq=operator.eq)
| 29 | return 2 * R * atan2(sqrt(a), sqrt(1 - a)) |
| 30 | |
| 31 | def lcs(l1, l2, eq=operator.eq): |
| 32 | """Finds the longest common subsequence of l1 and l2. |
| 33 | Returns a list of common parts and a list of differences. |
| 34 | |
| 35 | >>> lcs([1, 2, 3], [2]) |
| 36 | ([2], [1, 3]) |
| 37 | >>> lcs([1, 2, 3, 3, 4], [2, 3, 4, 5]) |
| 38 | ([2, 3, 4], [1, 3, 5]) |
| 39 | >>> lcs('banana', 'baraban') |
| 40 | (['b', 'a', 'a', 'n'], ['a', 'r', 'b', 'n', 'a']) |
| 41 | >>> lcs('abraban', 'banana') |
| 42 | (['b', 'a', 'a', 'n'], ['a', 'r', 'n', 'b', 'a']) |
| 43 | >>> lcs([1, 2, 3], [4, 5]) |
| 44 | ([], [4, 5, 1, 2, 3]) |
| 45 | >>> lcs([4, 5], [1, 2, 3]) |
| 46 | ([], [1, 2, 3, 4, 5]) |
| 47 | """ |
| 48 | prefs_len = [ |
| 49 | [0] * (len(l2) + 1) |
| 50 | for _ in range(len(l1) + 1) |
| 51 | ] |
| 52 | for i in range(1, len(l1) + 1): |
| 53 | for j in range(1, len(l2) + 1): |
| 54 | if eq(l1[i - 1], l2[j - 1]): |
| 55 | prefs_len[i][j] = prefs_len[i - 1][j - 1] + 1 |
| 56 | else: |
| 57 | prefs_len[i][j] = max(prefs_len[i - 1][j], prefs_len[i][j - 1]) |
| 58 | common = [] |
| 59 | diff = [] |
| 60 | i, j = len(l1), len(l2) |
| 61 | while i and j: |
| 62 | assert i >= 0 |
| 63 | assert j >= 0 |
| 64 | if eq(l1[i - 1], l2[j - 1]): |
| 65 | common.append(l1[i - 1]) |
| 66 | i -= 1 |
| 67 | j -= 1 |
| 68 | elif prefs_len[i - 1][j] >= prefs_len[i][j - 1]: |
| 69 | i -= 1 |
| 70 | diff.append(l1[i]) |
| 71 | else: |
| 72 | j -= 1 |
| 73 | diff.append(l2[j]) |
| 74 | diff.extend(reversed(l1[:i])) |
| 75 | diff.extend(reversed(l2[:j])) |
| 76 | return common[::-1], diff[::-1] |
| 77 | |
| 78 | def almost_equal(s1, s2, eps=1e-5): |
| 79 | """ |