106 lines
2.5 KiB
Rust
106 lines
2.5 KiB
Rust
use std::collections::HashMap;
|
|
use std::convert::TryInto;
|
|
|
|
struct Node {
|
|
length: isize,
|
|
edges: HashMap<u8, usize>,
|
|
suffix: usize,
|
|
}
|
|
|
|
impl Node {
|
|
fn new(length: isize, suffix: usize) -> Self {
|
|
Node {
|
|
length,
|
|
suffix,
|
|
edges: HashMap::new(),
|
|
}
|
|
}
|
|
}
|
|
|
|
const EVEN_ROOT: usize = 0;
|
|
const ODD_ROOT: usize = 1;
|
|
|
|
fn eertree(s: &[u8]) -> Vec<Node> {
|
|
let mut tree = vec![
|
|
Node::new(0, ODD_ROOT), // even root
|
|
Node::new(-1, ODD_ROOT), // odd root
|
|
];
|
|
|
|
let mut suffix = ODD_ROOT;
|
|
|
|
for (i, &c) in s.iter().enumerate() {
|
|
let mut n = suffix;
|
|
let mut k;
|
|
|
|
loop {
|
|
k = tree[n].length;
|
|
let k_plus_one: usize = (k + 1).try_into().unwrap_or(0);
|
|
if let Some(b) = i.checked_sub(k_plus_one) {
|
|
if b < s.len() && s[b] == c {
|
|
break;
|
|
}
|
|
}
|
|
n = tree[n].suffix;
|
|
}
|
|
|
|
if tree[n].edges.contains_key(&c) {
|
|
suffix = tree[n].edges[&c];
|
|
continue;
|
|
}
|
|
|
|
suffix = tree.len();
|
|
tree.push(Node::new(k + 2, 0));
|
|
tree[n].edges.insert(c, suffix);
|
|
|
|
if tree[suffix].length == 1 {
|
|
tree[suffix].suffix = EVEN_ROOT;
|
|
continue;
|
|
}
|
|
|
|
loop {
|
|
n = tree[n].suffix;
|
|
let tree_n_length_plus_one: usize = (tree[n].length + 1).try_into().unwrap_or(0);
|
|
if let Some(b) = i.checked_sub(tree_n_length_plus_one) {
|
|
if b < s.len() && s[b] == c {
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
|
|
tree[suffix].suffix = tree[n].edges[&c];
|
|
}
|
|
|
|
tree
|
|
}
|
|
|
|
fn sub_palindromes(tree: &[Node]) -> Vec<String> {
|
|
let mut result = Vec::new();
|
|
fn children(node: usize, p: String, tree: &[Node], result: &mut Vec<String>) {
|
|
for (&c, &n) in &tree[node].edges {
|
|
let c = c as char;
|
|
let p_new = format!("{}{}{}", c, p, c);
|
|
result.push(p_new.clone());
|
|
children(n, p_new, tree, result);
|
|
}
|
|
}
|
|
|
|
children(EVEN_ROOT, String::new(), tree, &mut result);
|
|
|
|
for (&c, &n) in &tree[ODD_ROOT].edges {
|
|
let c = c as char;
|
|
let p = c.to_string();
|
|
result.push(p.clone());
|
|
children(n, p, tree, &mut result);
|
|
}
|
|
|
|
result
|
|
}
|
|
|
|
fn main() {
|
|
let tree = eertree(b"eertree");
|
|
let palindromes = sub_palindromes(&tree);
|
|
for palindrome in palindromes {
|
|
println!("{}", palindrome);
|
|
}
|
|
}
|