================
@@ -156,3 +156,80 @@ def get_variable_metrics(
"missing_values": ScalarMetric(num_missing_values, improves_asc=False),
}
return metrics
+
+
+def lcs_len(a: List[int], b: List[int]) -> int:
+ """Returns the length of the longest common subsequence between a and b."""
+ lcs_table: List[List[int]] = [
+ [0 for _ in range(len(b) + 1)] for _ in range(len(a) + 1)
+ ]
+ for a_idx in range(len(a)):
+ for b_idx in range(len(b)):
+ if a[a_idx] == b[b_idx]:
+ lcs_table[a_idx + 1][b_idx + 1] = 1 + lcs_table[a_idx][b_idx]
+ else:
+ lcs_table[a_idx + 1][b_idx + 1] = max(
+ lcs_table[a_idx + 1][b_idx], lcs_table[a_idx][b_idx + 1]
+ )
+ return lcs_table[-1][-1]
----------------
OCHyams wrote:
Feels like the kind of thing we'd want some kind of unit test for, but I don't
think there's precedent for that in dexter! I didn't dry-run this or anything
but code looks fine and impl looks semantically same as some other references
https://github.com/llvm/llvm-project/pull/203844
_______________________________________________
llvm-branch-commits mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
