最长公共子序列

1. /// Longest common subsequence via Dynamic Programming

3. /// longest_common_subsequence(a, b) returns the longest common subsequence
4. /// between the strings a and b.
5. pub fn longest_common_subsequence(a: &str, b: &str) -> String {
6. let a: Vec<_> = a.chars().collect();
7. let b: Vec<_> = b.chars().collect();
8. let (na, nb) = (a.len(), b.len());

10. // solutions[i][j] is the length of the longest common subsequence
11. // between a[0..i-1] and b[0..j-1]
12. let mut solutions = vec![vec![0; nb + 1]; na + 1];

14. for (i, ci) in a.iter().enumerate() {
15. for (j, cj) in b.iter().enumerate() {
16. // if ci == cj, there is a new common character;
17. // otherwise, take the best of the two solutions
18. // at (i-1,j) and (i,j-1)
19. solutions[i + 1][j + 1] = if ci == cj {
20. solutions[i][j] + 1
21. } else {
22. solutions[i][j + 1].max(solutions[i + 1][j])
23. }
24. }
25. }

27. // reconstitute the solution string from the lengths
28. let mut result: Vec<char> = Vec::new();
29. let (mut i, mut j) = (na, nb);
30. while i > 0 && j > 0 {
31. if a[i - 1] == b[j - 1] {
32. result.push(a[i - 1]);
33. i -= 1;
34. j -= 1;
35. } else if solutions[i - 1][j] > solutions[i][j - 1] {
36. i -= 1;
37. } else {
38. j -= 1;
39. }
40. }

42. result.reverse();
43. result.iter().collect()
44. }

46. #[cfg(test)]
47. mod tests {
48. use super::longest_common_subsequence;

50. #[test]
51. fn test_longest_common_subsequence() {
52. // empty case
53. assert_eq!(&longest_common_subsequence("", ""), "");
54. assert_eq!(&longest_common_subsequence("", "abcd"), "");
55. assert_eq!(&longest_common_subsequence("abcd", ""), "");

57. // simple cases
58. assert_eq!(&longest_common_subsequence("abcd", "c"), "c");
59. assert_eq!(&longest_common_subsequence("abcd", "d"), "d");
60. assert_eq!(&longest_common_subsequence("abcd", "e"), "");
61. assert_eq!(&longest_common_subsequence("abcdefghi", "acegi"), "acegi");

63. // less simple cases
64. assert_eq!(&longest_common_subsequence("abcdgh", "aedfhr"), "adh");
65. assert_eq!(&longest_common_subsequence("aggtab", "gxtxayb"), "gtab");

67. // unicode
68. assert_eq!(
69. &longest_common_subsequence("你好，世界", "再见世界"),
70. "世界"
71. );
72. }
73. }