// BFS + 枝狩り // ---------- begin chmin, chmax ---------- pub trait ChangeMinMax { fn chmin(&mut self, x: Self) -> bool; fn chmax(&mut self, x: Self) -> bool; } impl ChangeMinMax for T { fn chmin(&mut self, x: Self) -> bool { *self > x && { *self = x; true } } fn chmax(&mut self, x: Self) -> bool { *self < x && { *self = x; true } } } // ---------- end chmin, chmax ---------- // ---------- begin z_algorithm ---------- fn z_algorithm(s: &[T]) -> Vec { let len = s.len(); let mut a = vec![0; len]; a[0] = len; let mut i = 1; let mut j = 0; while i < len { while i + j < len && s[j] == s[i + j] { j += 1; } a[i] = j; if j == 0 { i += 1; continue; } let mut k = 1; while i + k < len && k + a[k] < j { a[i + k] = a[k]; k += 1; } i += k; j -= k; } a } // ---------- end z_algorithm ---------- fn read() -> Vec { let mut s = String::new(); std::io::stdin().read_line(&mut s).unwrap(); let s = s.trim().chars().collect::>(); assert!(1 <= s.len() && s.len() <= 200000); assert!(s.iter().all(|s| "ab".contains(*s))); s } fn main() { let s = read(); let za = z_algorithm(&s); let mut su = za.clone(); for i in (1..su.len()).rev() { su[i - 1] = su[i - 1].max(su[i]); } let inf = s.len() + 1; let mut map = std::collections::HashMap::new(); let mut q = std::collections::VecDeque::new(); q.push_back((0, 0, true)); map.insert((0, 0, true), 0); let mut ans = s.len(); while let Some((x, y, used)) = q.pop_front() { if x == s.len() { ans = map[&(x, y, used)]; break; } let d = map[&(x, y, used)] + 1; if map.entry((x + 1, y, used)).or_insert(inf).chmin(d) { q.push_back((x + 1, y, used)); } if x > y && used && su[x] >= x && map.entry((x, x, false)).or_insert(inf).chmin(d) { q.push_back((x, x, false)); } if za[x] >= y && map.entry((x + y, y, true)).or_insert(inf).chmin(d) { q.push_back((x + y, y, true)); } } println!("{}", ans); }