AtCoder Beginner Contest 346 F

https://atcoder.jp/contests/abc346/tasks/abc346_f

直接kを求めるのは難しいですが、kを与えて部分列かを調べるのは比較的易しいので、二分探索を行います。

// SSttrriinngg in StringString
#![allow(non_snake_case)]

use std::collections::HashMap;


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}


//////////////////// PosDict ////////////////////

type Pos = (usize, usize);

struct PosDict {
    N: usize,
    dic: HashMap<char, Vec<usize>>,
    L: usize,
}

impl PosDict {
    fn create(N: usize, S: String) -> PosDict {
        let mut dic: HashMap<char, Vec<usize>> = HashMap::new();
        for (p, c) in S.chars().enumerate() {
            let e = dic.entry(c).or_insert(vec![]);
            (*e).push(p)
        }
        PosDict { N, dic, L: S.len() }
    }
    
    fn is_subsequence(&self, k: usize, T: &String) -> bool {
        let mut pos = (0, 0);
        for c in T.chars() {
            let res = self.find_last(pos, c, k);
            if res.is_none() {
                return false
            }
            else {
                pos = self.next_pos(res.unwrap())
            }
        }
        true
    }
    
    fn next_pos(&self, pos: Pos) -> Pos {
        if pos.1 < self.L - 1 {
            return (pos.0, pos.1 + 1)
        }
        else {
            return (pos.0 + 1, 0)
        }
    }
    
    fn find_last(&self, pos: Pos, c: char, k: usize) -> Option<Pos> {
        match self.dic.get(&c) {
            None    => None,
            Some(v) => self.find_char_pos(pos, v, k)
        }
    }
    
    fn find_char_pos(&self, pos: Pos, v: &Vec<usize>, k: usize) -> Option<Pos> {
        if pos.0 >= self.N {
            return None
        }
        
        let p1 = pos.1;
        let i1 = self.bin_search(0, v.len()-1, p1, v);
        let k1 = v.len() - i1;
        if k1 >= k {
            return Some((pos.0, v[i1+k-1]))
        }
        
        if v.len() * (self.N - pos.0 - 1) < k - k1 {
            return None
        }
        
        let q = (k + i1 - 1) / v.len();
        let r = (k + i1 - 1) % v.len();
        Some((pos.0 + q, v[r]))
    }
    
    // [first, last]
    fn bin_search(&self, first: usize, last: usize,
                        pos: usize, v: &Vec<usize>) -> usize {
        if pos > v[last] {
            v.len()
        }
        else if last - first < 2 {
            if v[first] < pos {
                last
            }
            else {
                first
            }
        }
        else {
            let mid = (first + last) / 2;
            if v[mid] < pos {
                self.bin_search(mid, last, pos, v)
            }
            else {
                self.bin_search(first, mid, pos, v)
            }
        }
    }
}


//////////////////// process ////////////////////

fn read_input() -> (usize, String, String) {
    let N = read();
    let S = read();
    let T = read();
    (N, S, T)
}

fn bin_search(first: usize, last: usize, T: &String, dic: &PosDict) -> usize {
    if last - first == 1 {
        first
    }
    else {
        let mid = (first + last) / 2;
        if dic.is_subsequence(mid, T) {
            bin_search(mid, last, T, dic)
        }
        else {
            bin_search(first, mid, T, dic)
        }
    }
}

fn F(N: usize, S: String, T: String) -> usize {
    let L = S.len();
    let pos_dic = PosDict::create(N, S);
    bin_search(0, L * N / T.len() + 1, &T, &pos_dic)
}

fn main() {
    let (N, S, T) = read_input();
    println!("{}", F(N, S, T))
}