csd/
lcsre.rs

1/// Find the longest repeating non-overlapping substring in cstr
2///
3/// The `longest_repeated_substring` function takes a null-terminated string and its length as input and
4/// returns the longest repeated non-overlapping substring in the string.
5///
6/// Arguments:
7///
8/// * `sv`: A reference to a character array representing the input string. It is assumed that the
9///         string is null-terminated.
10///
11/// Returns:
12///
13/// The function `longest_repeated_substring` returns a string, which is the longest repeated substring
14/// in the given input string `cstr`.
15///
16/// # Examples
17///
18/// ```
19/// use csd::lcsre::longest_repeated_substring;
20///
21/// let cs = "+-00+-00+-00+-0";
22/// assert_eq!(longest_repeated_substring(&cs), "+-00+-0");
23/// let cs = "abcdefgh";
24/// assert_eq!(longest_repeated_substring(&cs), "");
25/// ```
26#[allow(dead_code)]
27pub fn longest_repeated_substring(sv: &str) -> String {
28    let ndim = sv.len() + 1; // Dimension for the DP table (n+1 x n+1)
29    let mut lcsre = vec![vec![0usize; ndim]; ndim]; // DP table initialized with zeros
30
31    let mut res_length = 0; // To store length of the longest found substring
32
33    // Building table in bottom-up manner
34    let mut index = 0; // To store the starting index of the result substring
35    for i in 1..ndim {
36        for j in i + 1..ndim {
37            // Check if characters match and the substring wouldn't overlap
38            // (j-i) > lcsre[i-1][j-1] ensures non-overlapping condition
39            if sv.chars().nth(i - 1) == sv.chars().nth(j - 1) && lcsre[i - 1][j - 1] < (j - i) {
40                lcsre[i][j] = lcsre[i - 1][j - 1] + 1; // Extend the length of the common substring
41
42                // Update maximum length and starting index if we found a longer substring
43                if lcsre[i][j] > res_length {
44                    res_length = lcsre[i][j];
45                    index = i; // Store the ending index of the substring
46                }
47            } else {
48                lcsre[i][j] = 0; // Reset length if characters don't match
49            }
50        }
51    }
52
53    // Constructing the result substring if there's a non-empty result
54    if res_length > 0 {
55        // Extract substring from (index - length) to index
56        sv[index - res_length..index].to_string()
57    } else {
58        "".to_string() // Return empty string if no repeated substring found
59    }
60}
61
62#[cfg(test)]
63mod tests {
64    use super::*;
65
66    #[test]
67    fn test_lcsre() {
68        let cstr = "+-00+-00+-00+-0";
69        let res = longest_repeated_substring(cstr);
70        assert_eq!(res, "+-00+-0");
71        let cstr = "abcdefgh";
72        let res = longest_repeated_substring(cstr);
73        assert_eq!(res, "");
74        let cstr = "banana";
75        let res = longest_repeated_substring(cstr);
76        assert_eq!(res, "an");
77        let cstr = "";
78        let res = longest_repeated_substring(cstr);
79        assert_eq!(res, "");
80        let cstr = "aaaaa";
81        let res = longest_repeated_substring(cstr);
82        assert_eq!(res, "aa");
83        let cstr = "ababa";
84        let res = longest_repeated_substring(cstr);
85        assert_eq!(res, "ab");
86    }
87}
csd/lcsre.rs

csd/
lcsre.rs
