haar_lib/algo/
run_enumerate.rs

1//! Runの列挙
2//!
3//! # Problems
4//! - <https://judge.yosupo.jp/problem/runenumerate>
5use std::collections::{btree_map::Entry, BTreeMap};
6
7use crate::algo::zalgo::*;
8
9/// 文字列のrunを列挙する。
10pub fn run_enumerate<T: PartialEq + Clone>(mut s: Vec<T>) -> Vec<(usize, usize, usize)> {
11    let mut result = vec![];
12    let n = s.len();
13
14    run(&mut result, &s, 0);
15
16    let a = zalgo(&s);
17    a.into_iter()
18        .enumerate()
19        .skip(1)
20        .filter(|(i, x)| i <= x)
21        .for_each(|(i, x)| result.push((i, 0, i + x)));
22
23    s.reverse();
24    let a = zalgo(&s);
25    a.into_iter()
26        .enumerate()
27        .skip(1)
28        .filter(|(i, x)| i <= x)
29        .for_each(|(i, x)| result.push((i, n - i - x, n)));
30
31    let mut m = BTreeMap::<(usize, usize), usize>::new();
32
33    for (t, l, r) in result {
34        let p = (l, r);
35
36        match m.entry(p) {
37            Entry::Occupied(mut x) => {
38                x.insert((*x.get()).min(t));
39            }
40            Entry::Vacant(x) => {
41                x.insert(t);
42            }
43        }
44    }
45
46    let mut result: Vec<_> = m.into_iter().map(|((l, r), t)| (t, l, r)).collect();
47    result.sort();
48    result
49}
50
51fn run<T: PartialEq + Clone>(result: &mut Vec<(usize, usize, usize)>, s: &[T], left: usize) {
52    if s.len() <= 1 {
53        return;
54    }
55
56    let n = s.len();
57    let m = n / 2;
58    let first = &s[0..m];
59    let second = &s[m..];
60
61    let res = aux(first.to_vec(), second.to_vec());
62    result.extend(res.into_iter().map(|(t, l, r)| (t, left + l, left + r)));
63
64    let res = aux(
65        second.iter().rev().cloned().collect(),
66        first.iter().rev().cloned().collect(),
67    );
68    result.extend(
69        res.into_iter()
70            .map(|(t, l, r)| (t, left + n - r, left + n - l)),
71    );
72
73    run(result, first, left);
74    run(result, second, left + m);
75}
76
77fn aux<T: PartialEq + Clone>(first: Vec<T>, second: Vec<T>) -> Vec<(usize, usize, usize)> {
78    let mut ret = vec![];
79
80    let n = first.len();
81    let m = second.len();
82
83    let a = zalgo(&first.iter().rev().cloned().collect::<Vec<_>>());
84
85    let t = second
86        .clone()
87        .into_iter()
88        .map(Some)
89        .chain(std::iter::once(None))
90        .chain(first.into_iter().map(Some))
91        .chain(second.into_iter().map(Some))
92        .collect::<Vec<_>>();
93    let b = zalgo(&t);
94
95    for i in 1..n {
96        let l1 = a[i];
97        let l2 = b[n + m - i + 1];
98
99        if l1 + i == n || l2 == m || i > l1 + l2 {
100            continue;
101        }
102
103        let l = n - i - l1;
104        let r = n + l2;
105        let t = i;
106        ret.push((t, l, r));
107    }
108
109    ret
110}
haar_lib/algo/run_enumerate.rs

haar_lib/algo/
run_enumerate.rs
