// codesnip-guard: StringSearch
#[cfg_attr(any(),rustfmt::skip)]pub use self::string_search::{MultipleStringSearch,StringSearch};#[cfg_attr(any(),rustfmt::skip)]mod string_search{use super::{RangeMinimumQuery,SuffixArray};use std::{cmp::Ordering,ops::Range};#[derive(Clone,Debug,Eq,PartialEq,Ord,PartialOrd)]enum Delimited<T>{Separator(usize),Value(T)}trait Pattern<T>{fn len(&self)->usize;fn eq_text(&self,index:usize,text:&T)->bool;fn cmp_text(&self,index:usize,text:&T)->Ordering;}impl<T>Pattern<T>for[T]where T:Ord{fn len(&self)->usize{self.len()}fn eq_text(&self,index:usize,text:&T)->bool{text==&self[index]}fn cmp_text(&self,index:usize,text:&T)->Ordering{text.cmp(&self[index])}}struct DelimitedPattern<'a,T>{pattern:&'a[T]}impl<T>Pattern<Delimited<T>>for DelimitedPattern<'_,T>where T:Ord{fn len(&self)->usize{self.pattern.len()}fn eq_text(&self,index:usize,text:&Delimited<T>)->bool{matches!(text,Delimited::Value(value)if value==&self.pattern[index])}fn cmp_text(&self,index:usize,text:&Delimited<T>)->Ordering{match text{Delimited::Separator(_)=>Ordering::Less,Delimited::Value(value)=>value.cmp(&self.pattern[index]),}}}#[derive(Debug)]pub struct StringSearch<T>{text:Vec<T>,suffix_array:SuffixArray,lcp_array:Vec<usize>,rank:Vec<usize>,rmq:RangeMinimumQuery<usize>}impl<T>StringSearch<T>where T:Ord{pub fn new(text:Vec<T>)->Self{let suffix_array=SuffixArray::new(&text);let(lcp_array,rank)=suffix_array.lcp_array_with_rank(&text);let rmq=RangeMinimumQuery::new(lcp_array.clone());Self{text,suffix_array,lcp_array,rank,rmq}}pub fn text(&self)->&[T]{&self.text}pub fn suffix_array(&self)->&SuffixArray{&self.suffix_array}pub fn lcp_array(&self)->&[usize]{&self.lcp_array}pub fn rank(&self)->&[usize]{&self.rank}pub fn longest_common_prefix(&self,a:Range<usize>,b:Range<usize>)->usize{debug_assert!(a.start<=a.end&&a.end<=self.text.len());debug_assert!(b.start<=b.end&&b.end<=self.text.len());let len=(a.end-a.start).min(b.end-b.start);self.lcp_suffix(a.start,b.start).min(len)}pub fn compare(&self,a:Range<usize>,b:Range<usize>)->Ordering{debug_assert!(a.start<=a.end&&a.end<=self.text.len());debug_assert!(b.start<=b.end&&b.end<=self.text.len());let len_a=a.end-a.start;let len_b=b.end-b.start;let len=len_a.min(len_b);let lcp=self.lcp_suffix(a.start,b.start).min(len);if lcp==len{return len_a.cmp(&len_b);}self.text[a.start+lcp].cmp(&self.text[b.start+lcp])}pub fn range(&self,pattern:&[T])->Range<usize>{let left=self.bound_prefix(pattern,false);let right=self.bound_prefix(pattern,true);left..right}pub fn positions(&self,range:Range<usize>)->impl DoubleEndedIterator<Item=usize>+'_{debug_assert!(range.start<=range.end);debug_assert!(range.end<=self.text.len()+1);range.map(move|i|self.suffix_array[i])}pub fn kth_substrings(&self)->KthSubstrings<'_,T>{KthSubstrings::new(self)}fn lcp_suffix(&self,a:usize,b:usize)->usize{self.lcp_sa(self.rank[a],self.rank[b])}fn lcp_sa(&self,a:usize,b:usize)->usize{if a==b{return self.text.len()-self.suffix_array[a];}let(l,r)=if a<b{(a,b)}else{(b,a)};self.rmq.fold(l,r)}fn compare_suffix_pattern<P>(&self,suffix_start:usize,pattern:&P,start:usize)->(Ordering,usize)where P:Pattern<T>+?Sized{let n=self.text.len();let m=pattern.len();let mut i=start;while i<m&&suffix_start+i<n&&pattern.eq_text(i,&self.text[suffix_start+i]){i+=1;}let ord=if i==m{Ordering::Equal}else if suffix_start+i==n{Ordering::Less}else{pattern.cmp_text(i,&self.text[suffix_start+i])};(ord,i)}fn bound_prefix<P>(&self,pattern:&P,upper:bool)->usize where P:Pattern<T>+?Sized{if pattern.len()==0{return if upper{self.text.len()+1}else{0};}let pred=|ord:Ordering|{if upper{ord==Ordering::Greater}else{ord!=Ordering::Less}};let(cmp_last,lcp_last)=self.compare_suffix_pattern(self.suffix_array[self.text.len()],pattern,0);if!pred(cmp_last){return self.text.len()+1;}let mut l=0usize;let mut r=self.text.len();let mut lcp_l=0usize;let mut lcp_r=lcp_last;while r-l>1{let m=(l+r)>>1;let start=match lcp_l.cmp(&lcp_r){Ordering::Less=>lcp_l.min(self.lcp_sa(l,m)),Ordering::Greater=>lcp_r.min(self.lcp_sa(m,r)),Ordering::Equal=>lcp_l,};let(cmp_m,lcp_m)=self.compare_suffix_pattern(self.suffix_array[m],pattern,start);if pred(cmp_m){r=m;lcp_r=lcp_m;}else{l=m;lcp_l=lcp_m;}}r}fn geq_suffix(&self,range:Range<usize>)->usize{let n=self.text.len();debug_assert!(range.start<=range.end&&range.end<=n);let mut l=0usize;let mut r=n;while r-l>1{let m=(l+r)>>1;let ord=self.compare(self.suffix_array[m]..n,range.start..range.end);if matches!(ord,Ordering::Less){l=m;}else{r=m;}}r}}#[derive(Debug)]pub struct KthSubstrings<'a,T>{search:&'a StringSearch<T>,prefix:Vec<u64>}impl<'a,T>KthSubstrings<'a,T>where T:Ord{fn new(search:&'a StringSearch<T>)->Self{let n=search.text.len();let mut prefix=Vec::with_capacity(n+1);prefix.push(0);let mut total=0u64;for i in 1..=n{total+=(n-search.suffix_array[i]-search.lcp_array[i-1])as u64;prefix.push(total);}Self{search,prefix}}pub fn kth_distinct_substring(&self,k:u64)->Option<Range<usize>>{let idx=self.prefix.partition_point(|&x|x<=k);if idx==self.prefix.len(){return None;}debug_assert!(idx>0);let start=self.search.suffix_array[idx];let len=self.search.lcp_array[idx-1]+(k-self.prefix[idx-1])as usize+1;Some(start..start+len)}pub fn index_of_distinct_substring(&self,range:Range<usize>)->u64{debug_assert!(range.start<range.end&&range.end<=self.search.text.len());let m=range.len();let idx=self.search.geq_suffix(range);self.prefix[idx-1]+(m-self.search.lcp_array[idx-1]-1)as u64}}#[derive(Debug)]pub struct MultipleStringSearch<T>{texts:Vec<Vec<T>>,offsets:Vec<usize>,position_map:Vec<(usize,usize)>,search:StringSearch<Delimited<T>>}impl<T>MultipleStringSearch<T>where T:Ord+Clone{pub fn new(texts:Vec<Vec<T>>)->Self{assert!(!texts.is_empty());let total_len:usize=texts.iter().map(|text|text.len()+1).sum();let mut concat=Vec::with_capacity(total_len-1);let mut offsets=Vec::with_capacity(texts.len());let mut position_map=Vec::with_capacity(total_len);for(i,text)in texts.iter().enumerate(){offsets.push(concat.len());for(pos,value)in text.iter().cloned().enumerate(){concat.push(Delimited::Value(value));position_map.push((i,pos));}if i+1<texts.len(){concat.push(Delimited::Separator(!i));}position_map.push((i,text.len()));}let search=StringSearch::new(concat);Self{texts,offsets,position_map,search}}pub fn texts(&self)->&[Vec<T>]{&self.texts}pub fn longest_common_prefix(&self,a:(usize,Range<usize>),b:(usize,Range<usize>))->usize{let a=self.to_global_range(a);let b=self.to_global_range(b);self.search.longest_common_prefix(a,b)}pub fn compare(&self,a:(usize,Range<usize>),b:(usize,Range<usize>))->Ordering{let a=self.to_global_range(a);let b=self.to_global_range(b);self.search.compare(a,b)}pub fn range(&self,pattern:&[T])->Range<usize>{let pattern=DelimitedPattern{pattern};let left=self.search.bound_prefix(&pattern,false);let right=self.search.bound_prefix(&pattern,true);left..right}pub fn positions(&self,range:Range<usize>)->impl DoubleEndedIterator<Item=(usize,usize)>+'_{debug_assert!(range.start<=range.end);debug_assert!(range.end<=self.position_map.len());range.map(move|i|self.position_map[self.search.suffix_array[i]])}pub fn kth_substrings(&self)->MultipleKthSubstrings<'_,T>{MultipleKthSubstrings::new(self)}fn to_global_range(&self,(index,range):(usize,Range<usize>))->Range<usize>{debug_assert!(index<self.texts.len());let len=self.texts[index].len();debug_assert!(range.start<=range.end&&range.end<=len);let base=self.offsets[index];base+range.start..base+range.end}fn suffix_len(&self,a:usize)->usize{let(text_idx,pos)=self.position_map[self.search.suffix_array[a]];self.texts[text_idx].len()-pos}}#[derive(Debug)]pub struct MultipleKthSubstrings<'a,T>{search:&'a MultipleStringSearch<T>,prefix:Vec<u64>}impl<'a,T>MultipleKthSubstrings<'a,T>where T:Ord+Clone{fn new(search:&'a MultipleStringSearch<T>)->Self{let n=search.search.text.len();let mut prefix=Vec::with_capacity(n);prefix.push(0);let mut total=0u64;for i in 1..=n{let len=search.suffix_len(i);let prev_len=search.suffix_len(i-1);let lcp_prev=search.search.lcp_array[i-1].min(len).min(prev_len);total+=(len-lcp_prev)as u64;prefix.push(total);}Self{search,prefix}}pub fn kth_distinct_substring(&self,k:u64)->Option<(usize,Range<usize>)>{let idx=self.prefix.partition_point(|&x|x<=k);if idx==self.prefix.len(){return None;}let(text_idx,pos)=self.search.position_map[self.search.search.suffix_array[idx]];let len=self.search.suffix_len(idx)-(self.prefix[idx]-k)as usize+1;Some((text_idx,pos..pos+len))}pub fn index_of_distinct_substring(&self,(text_idx,range):(usize,Range<usize>))->u64{debug_assert!(text_idx<self.search.texts.len());debug_assert!(range.start<range.end&&range.end<=self.search.texts[text_idx].len());let m=range.len();let range=self.search.to_global_range((text_idx,range));let idx=self.search.search.geq_suffix(range);let len=self.search.suffix_len(idx);let prev_len=self.search.suffix_len(idx-1);let lcp_prev=self.search.search.lcp_array[idx-1].min(len).min(prev_len);self.prefix[idx-1]+(m-lcp_prev-1)as u64}}}
// codesnip-guard: RangeMinimumQuery
#[cfg_attr(any(),rustfmt::skip)]pub use self::range_minimum_query::RangeMinimumQuery;#[cfg_attr(any(),rustfmt::skip)]mod range_minimum_query{const BLOCK_SIZE:usize=64;#[derive(Clone,Debug)]pub struct RangeMinimumQuery<T>{data:Vec<T>,suffix:Vec<T>,prefix:Vec<T>,table:Vec<T>,blocks:usize}impl<T>RangeMinimumQuery<T>where T:Ord+Copy{pub fn new(data:Vec<T>)->Self{let n=data.len();let blocks=n.div_ceil(BLOCK_SIZE);if blocks==0{return Self{data,suffix:vec![],prefix:vec![],table:vec![],blocks};}let levels=usize::BITS as usize-blocks.leading_zeros()as usize;let mut table=vec![data[0];levels*blocks];let mut prefix=Vec::with_capacity(n);let mut minimum=data[0];for(i,&value)in data.iter().enumerate(){minimum=if i%BLOCK_SIZE==0{value}else{minimum.min(value)};prefix.push(minimum);if i%BLOCK_SIZE==BLOCK_SIZE-1||i+1==n{table[i/BLOCK_SIZE]=minimum;}}let mut suffix=data.clone();for block in suffix.chunks_mut(BLOCK_SIZE){minimum=*block.last().unwrap();for value in block.iter_mut().rev(){minimum=minimum.min(*value);*value=minimum;}}for level in 1..levels{let current=level*blocks;let previous=current-blocks;let half=1<<(level-1);for i in 0..blocks-(1<<level)+1{table[current+i]=if table[previous+i]<table[previous+i+half]{table[previous+i]}else{table[previous+i+half]};}}Self{data,suffix,prefix,table,blocks}}#[inline]pub fn fold(&self,l:usize,r:usize)->T{let r=r-1;let left_block=l/BLOCK_SIZE;let right_block=r/BLOCK_SIZE;if left_block+1<right_block{let middle_blocks=right_block-left_block-1;let level=middle_blocks.ilog2()as usize;let offset=level*self.blocks;self.suffix[l].min(self.prefix[r]).min(self.table[offset+left_block+1]).min(self.table[offset+right_block-(1<<level)])}else if left_block<right_block{self.suffix[l].min(self.prefix[r])}else{*self.data[l..=r].iter().min().unwrap()}}}}
// codesnip-guard: SuffixArray
#[cfg_attr(any(),rustfmt::skip)]pub use self::suffix_array::SuffixArray;#[cfg_attr(any(),rustfmt::skip)]mod suffix_array{use std::ops::Index;#[derive(Clone,Debug)]pub struct SuffixArray{sa:Vec<usize>}impl SuffixArray{pub fn new<T>(text:&[T])->Self where T:Ord{let n=text.len();let mut ord:Vec<_>=(0..n).collect();ord.sort_unstable_by_key(|&i|&text[i]);let mut s=vec![0usize;n+1];let mut upper=0usize;for(k,&i)in ord.iter().enumerate(){if k==0||text[ord[k-1]]!=text[i]{upper+=1;}s[i]=upper;}s[n]=0;let sa=sa_is(&s,upper);Self{sa}}pub fn into_inner(self)->Vec<usize>{self.sa}pub fn lcp_array_with_rank<T>(&self,text:&[T])->(Vec<usize>,Vec<usize>)where T:PartialEq{let n=self.sa.len()-1;let mut rank=vec![0usize;n+1];for i in 0..=n{rank[self.sa[i]]=i;}let mut h=0usize;let mut lcp_array=vec![0usize;n];for i in 0..n{let r=rank[i]-1;let j=self.sa[r];while i+h<n&&j+h<n&&text[i+h]==text[j+h]{h+=1;}lcp_array[r]=h;h=h.saturating_sub(1);}(lcp_array,rank)}pub fn lcp_array<T>(&self,text:&[T])->Vec<usize>where T:PartialEq{self.lcp_array_with_rank(text).0}}impl Index<usize>for SuffixArray{type Output=usize;fn index(&self,index:usize)->&Self::Output{&self.sa[index]}}fn induced_sort(s:&[usize],upper:usize,is_s:&[bool],lms:&[usize])->Vec<usize>{let n=s.len();let mut sa=vec![!0usize;n];let mut bucket_size=vec![0usize;upper+1];for&c in s{bucket_size[c]+=1;}let mut bucket_tail=vec![0usize;upper+1];{let mut sum=0usize;for i in 0..=upper{sum+=bucket_size[i];bucket_tail[i]=sum;}}for&pos in lms.iter().rev(){let c=s[pos];bucket_tail[c]-=1;sa[bucket_tail[c]]=pos;}let mut bucket_head=vec![0usize;upper+1];{let mut sum=0usize;for i in 0..=upper{bucket_head[i]=sum;sum+=bucket_size[i];}}for i in 0..n{let v=sa[i];if v==!0||v==0{continue;}let p=v-1;if!is_s[p]{let c=s[p];sa[bucket_head[c]]=p;bucket_head[c]+=1;}}let mut bucket_tail=vec![0usize;upper+1];{let mut sum=0usize;for i in 0..=upper{sum+=bucket_size[i];bucket_tail[i]=sum;}}for i in(0..n).rev(){let v=sa[i];if v==!0||v==0{continue;}let p=v-1;if is_s[p]{let c=s[p];bucket_tail[c]-=1;sa[bucket_tail[c]]=p;}}sa}fn sa_is(s:&[usize],upper:usize)->Vec<usize>{let n=s.len();match n{0=>return vec![],1=>return vec![0],_=>{}}let mut is_s=vec![false;n];is_s[n-1]=true;for i in(0..n-1).rev(){is_s[i]=if s[i]<s[i+1]{true}else if s[i]>s[i+1]{false}else{is_s[i+1]};}let mut lms_map=vec![!0;n];let mut lms=vec![];for i in 1..n{if is_s[i]&&!is_s[i-1]{lms_map[i]=lms.len();lms.push(i);}}let mut sa=induced_sort(s,upper,&is_s,&lms);if lms.len()>1{let mut rec_s=vec![0usize;lms.len()];let mut rec_upper=0usize;let mut prev=!0usize;for&pos in&sa{if pos!=!0&&lms_map[pos]!=!0{if prev!=!0{let mut offset=0usize;loop{if s[prev+offset]!=s[pos+offset]||is_s[prev+offset]!=is_s[pos+offset]{rec_upper+=1;break;}if offset!=0{let prev_is_lms=lms_map[prev+offset]!=!0;let pos_is_lms=lms_map[pos+offset]!=!0;if prev_is_lms||pos_is_lms{rec_upper+=(prev_is_lms!=pos_is_lms)as usize;break;}}offset+=1;}}rec_s[lms_map[pos]]=rec_upper;prev=pos;}}let rec_sa=if rec_upper+1==lms.len(){let mut rec_sa=vec![0usize;lms.len()];for i in 0..lms.len(){rec_sa[rec_s[i]]=i;}rec_sa}else{sa_is(&rec_s,rec_upper)};let mut ordered_lms=Vec::with_capacity(lms.len());for&i in&rec_sa{ordered_lms.push(lms[i]);}sa=induced_sort(s,upper,&is_s,&ordered_lms);}sa}}
// codesnip-guard: binary_search
#[cfg_attr(any(),rustfmt::skip)]pub use self::binary_search::{Bisect,SliceBisectExt,binary_search,parallel_binary_search};#[cfg_attr(any(),rustfmt::skip)]mod binary_search{use std::cmp::Ordering;#[doc=" binary search helper"]pub trait Bisect:Clone{#[doc=" Return between two elements if search is not end."]fn bisect_middle_point(&self,other:&Self)->Option<Self>;}macro_rules!impl_bisect_unsigned{($($t:ty)*)=>{$(impl Bisect for$t{fn bisect_middle_point(&self,other:&Self)->Option<Self>{if self.abs_diff(*other)>1{Some(self.midpoint(*other))}else{None}}})*};}macro_rules!impl_bisect_signed{($($t:ty)*)=>{$(impl Bisect for$t{fn bisect_middle_point(&self,other:&Self)->Option<Self>{if self.signum()!=other.signum(){if match self.cmp(other){Ordering::Less=>self+1<*other,Ordering::Equal=>false,Ordering::Greater=>other+1<*self,}{Some((*self).midpoint(*other))}else{None}}else{if self.abs_diff(*other)>1{Some(self.midpoint(*other))}else{None}}}})*};}macro_rules!impl_bisect_float{($({$t:ident$u:ident$i:ident$e:expr})*)=>{$(impl Bisect for$t{fn bisect_middle_point(&self,other:&Self)->Option<Self>{fn to_float_ord(x:$t)->$i{let a=x.to_bits()as$i;a^(((a>>$e)as$u)>>1)as$i}fn from_float_ord(a:$i)->$t{$t::from_bits((a^(((a>>$e)as$u)>>1)as$i)as _)}<$i as Bisect>::bisect_middle_point(&to_float_ord(*self),&to_float_ord(*other)).map(from_float_ord)}})*};}impl_bisect_unsigned!(u8 u16 u32 u64 u128 usize);impl_bisect_signed!(i8 i16 i32 i64 i128 isize);impl_bisect_float!({f32 u32 i32 31}{f64 u64 i64 63});#[doc=" binary search for monotone segment"]#[doc=""]#[doc=" if `ok < err` then search [ok, err) where t(`ok`), t, t, .... t, t(`ret`), f,  ... f, f, f, `err`"]#[doc=""]#[doc=" if `err < ok` then search (err, ok] where `err`, f, f, f, ... f, t(`ret`), ... t, t, t(`ok`)"]pub fn binary_search<T,F>(mut f:F,mut ok:T,mut err:T)->T where T:Bisect,F:FnMut(&T)->bool{while let Some(m)=ok.bisect_middle_point(&err){if f(&m){ok=m;}else{err=m;}}ok}#[doc=" binary search for slice"]pub trait SliceBisectExt<T>{#[doc=" Returns the first element that satisfies a predicate."]fn find_bisect(&self,f:impl FnMut(&T)->bool)->Option<&T>;#[doc=" Returns the last element that satisfies a predicate."]fn rfind_bisect(&self,f:impl FnMut(&T)->bool)->Option<&T>;#[doc=" Returns the first index that satisfies a predicate."]#[doc=" if not found, returns `len()`."]fn position_bisect(&self,f:impl FnMut(&T)->bool)->usize;#[doc=" Returns the last index+1 that satisfies a predicate."]#[doc=" if not found, returns `0`."]fn rposition_bisect(&self,f:impl FnMut(&T)->bool)->usize;}impl<T>SliceBisectExt<T>for[T]{fn find_bisect(&self,f:impl FnMut(&T)->bool)->Option<&T>{self.get(self.position_bisect(f))}fn rfind_bisect(&self,f:impl FnMut(&T)->bool)->Option<&T>{let pos=self.rposition_bisect(f);if pos==0{None}else{self.get(pos-1)}}fn position_bisect(&self,mut f:impl FnMut(&T)->bool)->usize{binary_search(|i|f(&self[*i as usize]),self.len()as i64,-1)as usize}fn rposition_bisect(&self,mut f:impl FnMut(&T)->bool)->usize{binary_search(|i|f(&self[i-1]),0,self.len()+1)}}pub fn parallel_binary_search<T,F,G>(mut f:F,q:usize,ok:T,err:T)->Vec<T>where T:Bisect,F:FnMut(&[Option<T>])->G,G:Fn(usize)->bool{let mut ok=vec![ok;q];let mut err=vec![err;q];loop{let m:Vec<_>=ok.iter().zip(&err).map(|(ok,err)|ok.bisect_middle_point(err)).collect();if m.iter().all(|m|m.is_none()){break;}let g=f(&m);for(i,m)in m.into_iter().enumerate(){if let Some(m)=m{if g(i){ok[i]=m;}else{err[i]=m;}}}}ok}}