use std::io::Write; fn main() { input! { t: usize, ask: [(usize, usize, bytes, bytes); t], } let out = std::io::stdout(); let mut out = std::io::BufWriter::new(out.lock()); for (n, m, a, b) in ask { let mut pos = wildcard_matching(&a, &b); if pos.is_empty() { writeln!(out, "-1").ok(); continue; } let mut ans = vec![b'z'; n + 1]; let t = a .iter() .map(|a| if *a == b'?' { b'a' } else { *a }) .collect::>(); for i in pos.into_iter().rev() { let mut res = t.clone(); res[i..(i + m)].copy_from_slice(&b); ans = std::cmp::min(ans, res); } let ans = ans.into_iter().map(|c| c as char).collect::(); writeln!(out, "{}", ans).ok(); } } pub fn wildcard_matching(a: &[u8], b: &[u8]) -> Vec { let n = a.len(); let m = b.len(); assert!(m > 0); if n < m { return vec![]; } let mut map = std::collections::BTreeMap::new(); let a = a .iter() .map(|a| { if *a == b'?' { M::zero() } else { let po = map.entry(*a).or_insert_with(rand); M::from(*po) } }) .collect::>(); let b = b .iter() .map(|a| { if *a == b'?' { M::zero() } else { let po = map.entry(*a).or_insert_with(rand); M::from(*po) } }) .rev() .collect::>(); let mut s = vec![]; { let mut a = a.clone(); let mut b = b.clone(); a.iter_mut().for_each(|a| *a = *a * *a * *a); s.add_assign(&a.multiply(&b)); } { let mut a = a.clone(); let mut b = b.clone(); a.iter_mut().for_each(|a| *a = *a * *a); b.iter_mut().for_each(|a| *a = M::new(2) * *a * *a); s.sub_assign(&a.multiply(&b)); } { let mut a = a.clone(); let mut b = b.clone(); b.iter_mut().for_each(|a| *a = *a * *a * *a); s.add_assign(&a.multiply(&b)); } ((m - 1)..n) .filter(|x| s[*x].is_zero()) .map(|x| x - (m - 1)) .collect() } // ---------- begin input macro ---------- // reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 #[macro_export] macro_rules! input { (source = $s:expr, $($r:tt)*) => { let mut iter = $s.split_whitespace(); input_inner!{iter, $($r)*} }; ($($r:tt)*) => { let s = { use std::io::Read; let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); s }; let mut iter = s.split_whitespace(); input_inner!{iter, $($r)*} }; } #[macro_export] macro_rules! input_inner { ($iter:expr) => {}; ($iter:expr, ) => {}; ($iter:expr, $var:ident : $t:tt $($r:tt)*) => { let $var = read_value!($iter, $t); input_inner!{$iter $($r)*} }; } #[macro_export] macro_rules! read_value { ($iter:expr, ( $($t:tt),* )) => { ( $(read_value!($iter, $t)),* ) }; ($iter:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read_value!($iter, $t)).collect::>() }; ($iter:expr, chars) => { read_value!($iter, String).chars().collect::>() }; ($iter:expr, bytes) => { read_value!($iter, String).bytes().collect::>() }; ($iter:expr, usize1) => { read_value!($iter, usize) - 1 }; ($iter:expr, $t:ty) => { $iter.next().unwrap().parse::<$t>().expect("Parse error") }; } // ---------- end input macro ---------- // ---------- begin ModInt ---------- // モンゴメリ乗算を用いる // ほぼCodeforces用 // 注意 // new_unchecked は値xが 0 <= x < modulo であることを仮定 // ModInt の中身は正規化された値で持ってるので直接読んだり書いたりするとぶっ壊れる // 奇素数のみ mod modint { use std::marker::*; use std::ops::*; pub trait Modulo { fn modulo() -> u32; fn rem() -> u32; fn ini() -> u64; fn reduce(x: u64) -> u32 { debug_assert!(x < (Self::modulo() as u64) << 32); let b = (x as u32 * Self::rem()) as u64; let t = x + b * Self::modulo() as u64; let mut c = (t >> 32) as u32; if c >= Self::modulo() { c -= Self::modulo(); } c as u32 } } #[allow(dead_code)] pub enum Mod1_000_000_007 {} impl Modulo for Mod1_000_000_007 { fn modulo() -> u32 { 1_000_000_007 } fn rem() -> u32 { 2226617417 } fn ini() -> u64 { 582344008 } } #[allow(dead_code)] pub enum Mod998_244_353 {} impl Modulo for Mod998_244_353 { fn modulo() -> u32 { 998_244_353 } fn rem() -> u32 { 998244351 } fn ini() -> u64 { 932051910 } } #[allow(dead_code)] pub fn generate_umekomi_modulo(p: u32) { assert!( p < (1 << 31) && p > 2 && p & 1 == 1 && (2u32..).take_while(|v| v * v <= p).all(|k| p % k != 0) ); let mut t = 1u32; let mut s = !p + 1; let mut n = !0u32 >> 2; while n > 0 { if n & 1 == 1 { t *= s; } s *= s; n >>= 1; } let mut ini = (1u64 << 32) % p as u64; ini = (ini << 32) % p as u64; assert!(t * p == !0); println!("pub enum Mod{} {{}}", p); println!("impl Modulo for Mod{} {{", p); println!(" fn modulo() -> u32 {{"); println!(" {}", p); println!(" }}"); println!(" fn rem() -> u32 {{"); println!(" {}", t); println!(" }}"); println!(" fn ini() -> u64 {{"); println!(" {}", ini); println!(" }}"); println!("}}"); let mut f = vec![]; let mut n = p - 1; for i in 2.. { if i * i > n { break; } if n % i == 0 { f.push(i); while n % i == 0 { n /= i; } } } if n > 1 { f.push(n); } let mut order = 1; let mut n = p - 1; while n % 2 == 0 { n /= 2; order <<= 1; } let z = (2u64..) .find(|z| { f.iter() .all(|f| mod_pow(*z, ((p - 1) / *f) as u64, p as u64) != 1) }) .unwrap(); let zeta = mod_pow(z, ((p - 1) / order) as u64, p as u64); println!("impl transform::NTTFriendly for Mod{} {{", p); println!(" fn order() -> usize {{"); println!(" {}", order); println!(" }}"); println!(" fn zeta() -> u32 {{"); println!(" {}", zeta); println!(" }}"); println!("}}"); } pub struct ModInt(u32, PhantomData); impl Clone for ModInt { fn clone(&self) -> Self { ModInt::build(self.0) } } impl Copy for ModInt {} impl Add for ModInt { type Output = ModInt; fn add(self, rhs: Self) -> Self::Output { let mut d = self.0 + rhs.0; if d >= T::modulo() { d -= T::modulo(); } Self::build(d) } } impl AddAssign for ModInt { fn add_assign(&mut self, rhs: Self) { *self = *self + rhs; } } impl Sub for ModInt { type Output = ModInt; fn sub(self, rhs: Self) -> Self::Output { let mut d = self.0 - rhs.0; if self.0 < rhs.0 { d += T::modulo(); } Self::build(d) } } impl SubAssign for ModInt { fn sub_assign(&mut self, rhs: Self) { *self = *self - rhs; } } impl Mul for ModInt { type Output = ModInt; fn mul(self, rhs: Self) -> Self::Output { Self::build(T::reduce(self.0 as u64 * rhs.0 as u64)) } } impl MulAssign for ModInt { fn mul_assign(&mut self, rhs: Self) { *self = *self * rhs; } } impl Neg for ModInt { type Output = ModInt; fn neg(self) -> Self::Output { if self.0 == 0 { Self::zero() } else { Self::build(T::modulo() - self.0) } } } impl std::fmt::Display for ModInt { fn fmt<'a>(&self, f: &mut std::fmt::Formatter<'a>) -> std::fmt::Result { write!(f, "{}", self.get()) } } impl std::fmt::Debug for ModInt { fn fmt<'a>(&self, f: &mut std::fmt::Formatter<'a>) -> std::fmt::Result { write!(f, "{}", self.get()) } } impl std::str::FromStr for ModInt { type Err = std::num::ParseIntError; fn from_str(s: &str) -> Result { let val = s.parse::()?; Ok(ModInt::new(val)) } } impl From for ModInt { fn from(val: usize) -> ModInt { ModInt::new_unchecked((val % T::modulo() as usize) as u32) } } impl From for ModInt { fn from(val: u64) -> ModInt { ModInt::new_unchecked((val % T::modulo() as u64) as u32) } } impl From for ModInt { fn from(val: i64) -> ModInt { let m = T::modulo() as i64; ModInt::new((val % m + m) as u32) } } #[allow(dead_code)] impl ModInt { fn build(d: u32) -> Self { ModInt(d, PhantomData) } pub fn zero() -> Self { Self::build(0) } pub fn is_zero(&self) -> bool { self.0 == 0 } } #[allow(dead_code)] impl ModInt { pub fn new_unchecked(d: u32) -> Self { Self::build(T::reduce(d as u64 * T::ini())) } pub fn new(d: u32) -> Self { Self::new_unchecked(d % T::modulo()) } pub fn one() -> Self { Self::new_unchecked(1) } pub fn get(&self) -> u32 { T::reduce(self.0 as u64) } pub fn pow(&self, mut n: u64) -> Self { let mut t = Self::one(); let mut s = *self; while n > 0 { if n & 1 == 1 { t *= s; } s *= s; n >>= 1; } t } pub fn inv(&self) -> Self { assert!(!self.is_zero()); self.pow((T::modulo() - 2) as u64) } } pub fn mod_pow(mut r: u64, mut n: u64, m: u64) -> u64 { let mut t = 1 % m; while n > 0 { if n & 1 == 1 { t = t * r % m; } r = r * r % m; n >>= 1; } t } } // ---------- end ModInt ---------- // ---------- begin Precalc ---------- mod precalc { use super::modint::*; #[allow(dead_code)] pub struct Precalc { inv: Vec>, fact: Vec>, ifact: Vec>, } #[allow(dead_code)] impl Precalc { pub fn new(n: usize) -> Precalc { let mut inv = vec![ModInt::one(); n + 1]; let mut fact = vec![ModInt::one(); n + 1]; let mut ifact = vec![ModInt::one(); n + 1]; for i in 2..(n + 1) { fact[i] = fact[i - 1] * ModInt::new_unchecked(i as u32); } ifact[n] = fact[n].inv(); if n > 0 { inv[n] = ifact[n] * fact[n - 1]; } for i in (1..n).rev() { ifact[i] = ifact[i + 1] * ModInt::new_unchecked((i + 1) as u32); inv[i] = ifact[i] * fact[i - 1]; } Precalc { inv: inv, fact: fact, ifact: ifact, } } pub fn inv(&self, n: usize) -> ModInt { assert!(n > 0); self.inv[n] } pub fn fact(&self, n: usize) -> ModInt { self.fact[n] } pub fn ifact(&self, n: usize) -> ModInt { self.ifact[n] } pub fn perm(&self, n: usize, k: usize) -> ModInt { if k > n { return ModInt::zero(); } self.fact[n] * self.ifact[n - k] } pub fn comb(&self, n: usize, k: usize) -> ModInt { if k > n { return ModInt::zero(); } self.fact[n] * self.ifact[k] * self.ifact[n - k] } } } // ---------- end Precalc ---------- use modint::*; pub trait NTTFriendly: modint::Modulo { fn order() -> usize; fn zeta() -> u32; } type M = ModInt; impl NTTFriendly for Mod998_244_353 { fn order() -> usize { 8388608 } fn zeta() -> u32 { 15311432 } } // 列に対する命令をテキトーに詰めあわせ // modint, primitive type の2つあたりで使うことを想定 // +, -, * // zero を要求してないのに仮定してる場所がある // // 何も考えずに書き始めたらいろいろよくわからないことになった // 整理 // 長さが等しいときの加算、減算、dot積はok // 長さが異なるときはどうする? // 0埋めされてるというイメージなので // 加算、減算は素直だがdot積はイマイチ // dot積だけ長さが等しいとしておく? // あるいは0埋めのイメージを消すか use std::ops::*; pub trait Zero: Sized + Add { fn zero() -> Self; } pub fn zero() -> T { T::zero() } impl Zero for ModInt { fn zero() -> Self { Self::zero() } } impl Zero for usize { fn zero() -> Self { 0 } } pub trait ArrayAdd { type Item; fn add(&self, rhs: &[Self::Item]) -> Vec; } impl ArrayAdd for [T] where T: Zero + Copy, { type Item = T; fn add(&self, rhs: &[Self::Item]) -> Vec { let mut c = vec![T::zero(); self.len().max(rhs.len())]; c[..self.len()].copy_from_slice(self); c.add_assign(rhs); c } } pub trait ArrayAddAssign { type Item; fn add_assign(&mut self, rhs: &[Self::Item]); } impl ArrayAddAssign for [T] where T: Add + Copy, { type Item = T; fn add_assign(&mut self, rhs: &[Self::Item]) { assert!(self.len() >= rhs.len()); self.iter_mut().zip(rhs).for_each(|(x, a)| *x = *x + *a); } } impl ArrayAddAssign for Vec where T: Zero + Add + Copy, { type Item = T; fn add_assign(&mut self, rhs: &[Self::Item]) { if self.len() < rhs.len() { self.resize(rhs.len(), T::zero()); } self.as_mut_slice().add_assign(rhs); } } pub trait ArraySub { type Item; fn sub(&self, rhs: &[Self::Item]) -> Vec; } impl ArraySub for [T] where T: Zero + Sub + Copy, { type Item = T; fn sub(&self, rhs: &[Self::Item]) -> Vec { let mut c = vec![T::zero(); self.len().max(rhs.len())]; c[..self.len()].copy_from_slice(self); c.sub_assign(rhs); c } } pub trait ArraySubAssign { type Item; fn sub_assign(&mut self, rhs: &[Self::Item]); } impl ArraySubAssign for [T] where T: Sub + Copy, { type Item = T; fn sub_assign(&mut self, rhs: &[Self::Item]) { assert!(self.len() >= rhs.len()); self.iter_mut().zip(rhs).for_each(|(x, a)| *x = *x - *a); } } impl ArraySubAssign for Vec where T: Zero + Sub + Copy, { type Item = T; fn sub_assign(&mut self, rhs: &[Self::Item]) { if self.len() < rhs.len() { self.resize(rhs.len(), T::zero()); } self.as_mut_slice().sub_assign(rhs); } } pub trait ArrayDot { type Item; fn dot(&self, rhs: &[Self::Item]) -> Vec; } impl ArrayDot for [T] where T: Mul + Copy, { type Item = T; fn dot(&self, rhs: &[Self::Item]) -> Vec { assert!(self.len() == rhs.len()); self.iter().zip(rhs).map(|p| *p.0 * *p.1).collect() } } pub trait ArrayDotAssign { type Item; fn dot_assign(&mut self, rhs: &[Self::Item]); } impl ArrayDotAssign for [T] where T: MulAssign + Copy, { type Item = T; fn dot_assign(&mut self, rhs: &[Self::Item]) { assert!(self.len() == rhs.len()); self.iter_mut().zip(rhs).for_each(|(x, a)| *x *= *a); } } pub trait ArrayMul { type Item; fn mul(&self, rhs: &[Self::Item]) -> Vec; } impl ArrayMul for [T] where T: Zero + Mul + Copy, { type Item = T; fn mul(&self, rhs: &[Self::Item]) -> Vec { if self.is_empty() || rhs.is_empty() { return vec![]; } let mut res = vec![zero(); self.len() + rhs.len() - 1]; for (i, a) in self.iter().enumerate() { for (c, b) in res[i..].iter_mut().zip(rhs) { *c = *c + *a * *b; } } res } } pub trait ArrayNTT { type Item; fn ntt(&mut self); fn intt(&mut self); fn multiply(&self, rhs: &[Self::Item]) -> Vec; } impl ArrayNTT for [ModInt] where T: NTTFriendly, { type Item = ModInt; fn ntt(&mut self) { let f = self; let n = f.len(); assert!(n.count_ones() == 1); assert!(n <= T::order()); let len = n.trailing_zeros() as usize; let mut es = [ModInt::zero(); 30]; let mut ies = [ModInt::zero(); 30]; let mut sum_e = [ModInt::zero(); 30]; let cnt2 = T::order().trailing_zeros() as usize; let mut e = ModInt::new_unchecked(T::zeta()); let mut ie = e.inv(); for i in (2..=cnt2).rev() { es[i - 2] = e; ies[i - 2] = ie; e = e * e; ie = ie * ie; } let mut now = ModInt::one(); for i in 0..(cnt2 - 1) { sum_e[i] = es[i] * now; now *= ies[i]; } for ph in 1..=len { let p = 1 << (len - ph); let mut now = ModInt::one(); for (i, f) in f.chunks_exact_mut(2 * p).enumerate() { let (x, y) = f.split_at_mut(p); for (x, y) in x.iter_mut().zip(y.iter_mut()) { let l = *x; let r = *y * now; *x = l + r; *y = l - r; } now *= sum_e[(!i).trailing_zeros() as usize]; } } } fn intt(&mut self) { let f = self; let n = f.len(); assert!(n.count_ones() == 1); assert!(n <= T::order()); let len = n.trailing_zeros() as usize; let mut es = [ModInt::zero(); 30]; let mut ies = [ModInt::zero(); 30]; let mut sum_ie = [ModInt::zero(); 30]; let cnt2 = T::order().trailing_zeros() as usize; let mut e = ModInt::new_unchecked(T::zeta()); let mut ie = e.inv(); for i in (2..=cnt2).rev() { es[i - 2] = e; ies[i - 2] = ie; e = e * e; ie = ie * ie; } let mut now = ModInt::one(); for i in 0..(cnt2 - 1) { sum_ie[i] = ies[i] * now; now *= es[i]; } for ph in (1..=len).rev() { let p = 1 << (len - ph); let mut inow = ModInt::one(); for (i, f) in f.chunks_exact_mut(2 * p).enumerate() { let (x, y) = f.split_at_mut(p); for (x, y) in x.iter_mut().zip(y.iter_mut()) { let l = *x; let r = *y; *x = l + r; *y = (l - r) * inow; } inow *= sum_ie[(!i).trailing_zeros() as usize]; } } let ik = ModInt::new_unchecked((T::modulo() + 1) >> 1).pow(len as u64); for f in f.iter_mut() { *f *= ik; } } fn multiply(&self, rhs: &[Self::Item]) -> Vec { if self.len().min(rhs.len()) <= 32 { return self.mul(rhs); } let size = (self.len() + rhs.len() - 1).next_power_of_two(); let mut f = vec![ModInt::zero(); size]; let mut g = vec![ModInt::zero(); size]; f[..self.len()].copy_from_slice(self); g[..rhs.len()].copy_from_slice(rhs); f.ntt(); g.ntt(); f.dot_assign(&g); f.intt(); f.truncate(self.len() + rhs.len() - 1); f } } pub trait PolynomialOperation { type Item; fn eval(&self, x: Self::Item) -> Self::Item; fn derivative(&self) -> Vec; fn integral(&self) -> Vec; } impl PolynomialOperation for [ModInt] { type Item = ModInt; fn eval(&self, x: Self::Item) -> Self::Item { self.iter().rev().fold(ModInt::zero(), |s, a| s * x + *a) } fn derivative(&self) -> Vec { if self.len() <= 1 { return vec![]; } self[1..] .iter() .enumerate() .map(|(k, a)| ModInt::new_unchecked(k as u32 + 1) * *a) .collect() } fn integral(&self) -> Vec { if self.is_empty() { return vec![]; } let mut inv = vec![ModInt::one(); self.len() + 1]; let mut mul = ModInt::zero(); for i in 1..=self.len() { mul += ModInt::one(); inv[i] = inv[i - 1] * mul; } let mut prod = inv[self.len()].inv(); for i in (1..=self.len()).rev() { inv[i] = self[i - 1] * inv[i - 1] * prod; prod *= mul; mul -= ModInt::one(); } inv[0] = ModInt::zero(); inv } } pub trait FPSOperation { type Item; fn inverse(&self, n: usize) -> Vec; fn log(&self, n: usize) -> Vec; fn exp(&self, n: usize) -> Vec; } impl FPSOperation for [ModInt] { type Item = ModInt; fn inverse(&self, n: usize) -> Vec { assert!(self.len() > 0 && !self[0].is_zero()); let len = n.next_power_of_two(); assert!(2 * len <= T::order()); let mut b = vec![ModInt::zero(); n]; b[0] = self[0].inv(); let mut f = Vec::with_capacity(2 * len); let mut g = Vec::with_capacity(2 * len); let mut size = 1; while size < n { g.clear(); g.extend(b.iter().take(size)); g.resize(2 * size, ModInt::zero()); f.clear(); f.extend(self.iter().take(2 * size)); f.resize(2 * size, ModInt::zero()); f.ntt(); g.ntt(); f.dot_assign(&g); f.intt(); f[..size].iter_mut().for_each(|f| *f = ModInt::zero()); f.ntt(); f.dot_assign(&g); f.intt(); for (b, g) in b[size..].iter_mut().zip(&f[size..]) { *b = *b - *g; } size *= 2; } b } fn log(&self, n: usize) -> Vec { assert!(self.get(0).map_or(false, |p| p.get() == 1)); let mut b = self.derivative().multiply(&self.inverse(n)); b.truncate(n - 1); let mut b = b.integral(); b.resize(n, ModInt::zero()); b } fn exp(&self, n: usize) -> Vec { assert!(self.get(0).map_or(true, |a| a.is_zero())); assert!(n <= T::order()); let mut b = vec![ModInt::one()]; let mut size = 1; while size < n { size <<= 1; let f = b.log(size); let g = self[..self.len().min(size)].sub(&f); b = b.multiply(&g).add(&b); b.truncate(size); } b.truncate(n); b.resize(n, ModInt::zero()); b } } // test // yuki907: https://yukicoder.me/submissions/712523 // hhkb2020: https://atcoder.jp/contests/hhkb2020/submissions/26997806 // // ---------- begin rand ---------- fn rand_memory() -> usize { Box::into_raw(Box::new("I hope this is a random number")) as usize } fn rand() -> usize { static mut X: usize = 0; unsafe { if X == 0 { X = rand_memory(); } X ^= X << 13; X ^= X >> 17; X ^= X << 5; X } } fn shuffle(a: &mut [T]) { for i in 1..a.len() { let p = rand() % (i + 1); a.swap(i, p); } } // ---------- end rand ---------- pub struct SAString { s: Vec, sa: Vec, isa: Vec, lcp: Vec, rmq: RMQ, } impl SAString { pub fn new(s: Vec) -> Self { let (sa, isa, lcp) = suffix_array(&s); let rmq = RMQ::new(lcp.clone()); Self { s, sa, isa, lcp, rmq, } } pub fn find_lcp(&self, x: usize, y: usize) -> usize { assert!(x.max(y) < self.s.len()); if x == y { self.s.len() - x.max(y) } else { let a = self.isa[x.min(y)]; let b = self.isa[x.max(y)]; self.rmq.find(a.min(b) + 1, a.max(b) + 1) } } pub fn compare( &self, mut a: Vec<(usize, usize)>, mut b: Vec<(usize, usize)>, ) -> std::cmp::Ordering { assert!(a .iter() .chain(b.iter()) .all(|p| p.0 <= p.1 && p.1 <= self.s.len())); a.retain(|p| p.0 < p.1); b.retain(|p| p.0 < p.1); let mut x = 0; let mut y = 0; while x < a.len() && y < b.len() { let a = &mut a[x]; let b = &mut b[y]; let len = (a.1 - a.0).min(b.1 - b.0); let lcp = self.find_lcp(a.0, b.0).min(len); a.0 += lcp; b.0 += lcp; if a.0 < a.1 && b.0 < b.1 { return self.s[a.0].cmp(&self.s[b.0]); } if a.0 == a.1 { x += 1; } if b.0 == b.1 { y += 1; } } (x < a.len()).cmp(&(y < b.len())) } } // O(N (log N)^2) // 文字種によらない // O(N log N) の実装が悪く、log2つの方が早かったので一時的にこちらに更新 // ---------- begin suffix array ---------- fn suffix_array(s: &[T]) -> (Vec, Vec, Vec) { let n = s.len(); let mut z = s.iter().collect::>(); z.sort(); z.dedup(); let mut ord = Vec::with_capacity(n); for s in s.iter() { ord.push(z.binary_search(&s).unwrap() as u32 + 1); } let mut z = (0..n).map(|p| ((ord[p], 0), p)).collect::>(); z.sort_by_key(|p| p.0); let mut len = 1; while len < n { for z in z.iter_mut() { z.0 = (ord[z.1], ord.get(z.1 + len).map_or(0, |p| *p)); } z.sort_by_key(|p| p.0); let mut id = 1; let mut prev = z[0].0; for z in z.iter_mut() { if z.0 != prev { id += 1; prev = z.0; } ord[z.1] = id; } len <<= 1; } let sa = z.into_iter().map(|p| p.1).collect::>(); let mut isa = vec![0; s.len()]; for (i, sa) in sa.iter().enumerate() { isa[*sa] = i; } let mut lcp = vec![0; s.len()]; let mut h = 0; for i in 0..sa.len() { if isa[i] + 1 < sa.len() { let j = sa[isa[i] + 1]; while i.max(j) + h < sa.len() && s[i + h] == s[j + h] { h += 1; } lcp[isa[i] + 1] = h; if h > 0 { h -= 1; } } } (sa, isa, lcp) } // ---------- end suffix array ---------- pub struct RMQ { data: Vec, table: SparseTable, bit: Vec, } impl RMQ where T: Ord + Copy, { pub fn new(data: Vec) -> Self { assert!(!data.is_empty()); let mut bit = vec![0; data.len()]; let w = 8 * std::mem::size_of_val(&bit[0]); let mut stack: Vec = vec![]; let mut table_ini = Vec::with_capacity((data.len() + w - 1) / w); for (bit, data) in bit.chunks_mut(w).zip(data.chunks(w)) { stack.clear(); let mut b = 0; for (i, (bit, d)) in bit.iter_mut().zip(data.iter()).enumerate() { while stack.last().map_or(false, |x| data[*x] > *d) { b ^= 1 << stack.pop().unwrap(); } b |= 1 << i; *bit = b; stack.push(i); } table_ini.push(data[stack[0]]); } let table = SparseTable::new(table_ini); RMQ { data, table, bit } } pub fn find(&self, l: usize, r: usize) -> T { assert!(l < r && r <= self.data.len()); let w = 8 * std::mem::size_of_val(&self.bit[0]); let r = r - 1; let p = l / w; let q = r / w; if p == q { let pos = l + (self.bit[r] >> (l % w)).trailing_zeros() as usize; self.data[pos] } else { let lw = l + (self.bit[p * w + w - 1] >> (l % w)).trailing_zeros() as usize; let rw = q * w + self.bit[r].trailing_zeros() as usize; let mut res = std::cmp::min(self.data[lw], self.data[rw]); if p + 1 < q { res = std::cmp::min(res, self.table.find(p + 1, q)); } res } } } // ---------- begin sparse table (min) ---------- pub struct SparseTable { table: Vec>, size: usize, } impl SparseTable where T: Ord + Copy, { pub fn new(mut a: Vec) -> Self { assert!(a.len() > 0); let size = a.len(); let mut table = vec![]; let mut w = 1; while w + 1 <= a.len() { let next = a .iter() .zip(a[w..].iter()) .map(|p| std::cmp::min(*p.0, *p.1)) .collect::>(); table.push(a); a = next; w <<= 1; } table.push(a); SparseTable { table: table, size: size, } } pub fn find(&self, l: usize, r: usize) -> T { assert!(l < r && r <= self.size); let k = 8 * std::mem::size_of::() - 1 - (r - l).leading_zeros() as usize; let table = &self.table[k]; std::cmp::min(table[l], table[r - (1 << k)]) } } // ---------- end sparse table (min) ----------