mylibrary_/
algorithm.rs

1//!My algorithm collection
2
3///This `fn` uses **manacher's algorithm**
4pub fn longest_palindrome(s: String,) -> String {
5	let s_with_bogus = format!("|{}", s.chars().map(|c| c.to_string() + "|",).collect::<String>());
6	let (mut center, mut radius, len,) = (0, 0, s_with_bogus.len(),);
7	let mut palind_radii = vec![0; len];
8
9	while center < len {
10		while center - radius > 0
11			&& center + radius < len - 1
12			&& s_with_bogus[center - radius - 1..center - radius]
13				== s_with_bogus[center + radius + 1..center + radius + 2]
14		{
15			radius += 1;
16		}
17
18		palind_radii[center] = radius;
19
20		let (old_center, old_radius,) = (center, radius,);
21		center += 1;
22		radius = 0;
23		while center <= old_center + old_radius {
24			let mirrored_center = old_center - (center - old_center);
25			let max_mirrored_radi = old_center + old_radius - center;
26
27			if palind_radii[mirrored_center] < max_mirrored_radi {
28				palind_radii[center] = palind_radii[mirrored_center];
29				center += 1;
30			} else if palind_radii[mirrored_center] > max_mirrored_radi {
31				// NOTE: this is legal because max_mirrored_radi+1 has already proved ilegal
32				palind_radii[center] = max_mirrored_radi;
33
34				center += 1;
35			} else {
36				radius = max_mirrored_radi; //palind_radii[mirrored_center] = max_mirrored_radi
37				break;
38			}
39		}
40	}
41
42	radius = 0;
43	for (i, &r,) in palind_radii.iter().enumerate() {
44		if radius < r {
45			radius = r;
46			center = i;
47		}
48	}
49
50	s_with_bogus[center - radius..center + radius + 1].chars().filter(|&c| c != '|',).collect()
51}
52
53///See more detail at [here](https://leetcode.com/problems/regular-expression-matching/description/)
54///
55///This `fn` supports regular-expression-matching with . & * where:
56/// - '.' matches any single character
57/// - '*' matches zero or more of the preceding element
58///
59/// # Example
60///
61/// ```rust
62/// # use mylibrary_::algorithm::regex_match;
63/// assert_eq!(regex_match("bbbba".to_string(), ".*a*a".to_string()), true);
64/// assert_eq!(regex_match("a".to_string(), ".*..a*".to_string()), false);
65/// assert_eq!(regex_match("ab".to_string(), ".*..".to_string()), true);
66/// ```
67pub fn regex_match(s: String, p: String,) -> bool {
68	if p.is_empty() {
69		return s.is_empty();
70	}
71
72	let first_match = !s.is_empty()
73		&& (p.chars().nth(0,) == s.chars().nth(0,) || p.chars().nth(0,) == Some('.',));
74
75	if p.len() >= 2 && p.chars().nth(1,) == Some('*',) {
76		regex_match(s.clone(), p[2..].to_string(),)
77			|| (first_match && regex_match(s[1..].to_string(), p,))
78	} else {
79		first_match && regex_match(s[1..].to_string(), p[1..].to_string(),)
80	}
81}
mylibrary_/algorithm.rs

mylibrary_/
algorithm.rs
