Submission #2522756

---

Source Code Expand

use std::io::*;
use std::str::FromStr;

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

struct Solver {
    s: Vec<char>,
    skip: Vec<Vec<usize>>,
    memo: Vec<usize>,
}

impl Solver {
    fn new() -> Solver {
        let s = read::<String>().chars().collect::<Vec<char>>();
        let n = s.len();
        let mut skip = vec![vec![n + 10; 26]; n + 1];
        for i in (0..n).rev() {
            let c = (s[i] as u8 - 'a' as u8) as usize;
            skip[i] = skip[i + 1].clone();
            skip[i][c] = i;
        }
        Solver {
            s: s,
            skip: skip,
            memo: vec![n + 10; n + 10],
        }
    }
    fn calc(&mut self, pos: usize) -> usize {
        let n = self.s.len();
        if pos >= n + 10 {
            return 0;
        }
        if self.memo[pos] < n + 10 {
            return self.memo[pos];
        }
        let mut ret = n;
        for c in 0..26 {
            let npos = 1 + self.skip[pos][c];
            let nret = 1 + self.calc(npos);
            // println!("{} {} {}", c, npos, nret);
            ret = std::cmp::min(ret, nret);
        }
        self.memo[pos] = ret;
        ret
    }
    fn solve(&mut self) {
        let n = self.s.len();
        let len = self.calc(0);
        let mut ans = vec![];
        let mut pos = 0;
        while pos < n {
            for c in 0..26 {
                let npos = 1 + self.skip[pos][c];
                let nlen = self.calc(npos);
                if 1 + nlen + ans.len() == len {
                    ans.push(c);
                    pos = npos;
                    break;
                }
            }
        }
        for &c in ans.iter() {
            let v = (c as u8 + 'a' as u8) as char;
            print!("{}", v);
        }
        println!("");
    }
}

fn main() {
    let mut solver = Solver::new();
    solver.solve();
}

Submission Info

Judge Result