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)) }