1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

#![allow(dead_code)]

pub mod range;
pub mod token;
pub mod diff;

use std::cmp::max;

#[derive(Copy, Clone, PartialEq)]
pub enum Sensivity {
    CaseSensitive,
    CaseInsensitive,
}

pub (crate) fn create_2dim_vector(m: usize, n: usize) -> Vec<Vec<usize>> {
    let mut vec2dim: Vec<Vec<usize>> = Vec::with_capacity(m+1);
    {
        let mut dim2: Vec<usize> = Vec::with_capacity(n + 1);
        dim2.resize(n + 1, 0);
        vec2dim.resize(m + 1, dim2.clone());
    }
    vec2dim
}

/// Search common longest sequence in two text lines.
pub fn longest_common_sequence(str1: &[char], str2: &[char]) -> (String, usize) {
    let m = str1.len();
    let n = str2.len();

    if n == 0 || m == 0 {
        return ("".to_string(), 0);
    }

    // Prepare 2-dim vector for indexes.
    let mut lens = create_2dim_vector(m, n);

    for i in 0..m {
        for j in 0..n {
            if str1[i] == str2[j] {
                lens[i + 1][j + 1] = 1 + lens[i][j];
            }
            else {
                lens[i+1][j+1] = max(lens[i+1][j], lens[i][j+1]);
            }
        }
    }

    // buffer for characters of longest common sequence.
    let mut buffer: Vec<char> = Vec::new();

    let mut i = m - 1;
    let mut j = n - 1;
    loop {
        if str1[i] == str2[j] {
            buffer.push(str1[i]);
            i -= 1;
            j -= 1;
        } else if lens[i + 1][j] > lens[i][j + 1] {
            j -= 1;
        } else {
            i -= 1;
        }
        if i == 0 || j == 0 {
            break;
        }
    }

    (buffer.into_iter().rev().collect(), lens[m][n])
}