Ex - Substring Sort Editorial
by 
mechanicalpenciI
問題の条件を整理すると、対応する文字列は等しいが三つ組として異なるものについては列の中で入れ替える事ができ、逆に入れ替える事ができるものはそのようなものに限られる事が分かります。よって、この問題は \(S_K[L,R]\) の形で書かれる, \(M\) 個の文字列を辞書順に並べたときに、\(x_i\) 番目に来る文字列に対応する三つ組を求める問題である事がわかります。
\(S_i\) の部分文字列全体を辞書順にソートする事を考えます。
各(空でない)部分文字列はある \(S_K\) の suffix の prefix の \(1\) つとして一意に書く事ができることに注意します。
(具体的には、\(S_K[L,R]\) は \(S_K\) の suffix である \(S_K[L,|S_K|]\) の prefix です。)
1. Suffix array および Longest Common Prefix の配列を構築する
まず、 \(S_1,S_2, \ldots,S_N\) の suffix 全体 (これは \(\displaystyle\sum_{i=1}^N \lvert S_i\rvert\) 個の要素からなります ) をソートしてsuffix array のようなもの \(T\) を作ることを考えます。
すなわち、\(T=((K_1,L_1),\ldots, (K_{|T|},L_{|T|}))\) であって、 \(1\leq i\leq |T|\) について、\(i\leq j\)の時辞書順で \(S_{K_i}[L_i,|S_{K_i}|]\leq S_{K_j}[L_j,|S_{K_j}|]\) となるようなものを得る事を考えます。
これは、\(S_1, S_2, \ldots, S_N\) を、各文字列の末尾にどの文字よりも辞書順で小さい文字 (例えば $ ) を付け足した上で連結した文字列
\(S'=S_1+\) $ \(+S_2+\) $\( +\cdots +S_{N-1}+\) $ \(+S_N+\) $
を考え、この suffix array を求める事で得る事ができます。なぜなら、\(S'\) の各 suffix である \(S'[L_i,|S'|]\) について、文字列を前から見ていき、初めて現れた $ 以降を削除したような文字列\(\bar{S}_i\) を考えると、
\(S'[L_i,|S'|]\leq S'[L_j,|S'|]\) のとき \(\bar{S}_i\leq \bar{S}_j\) が成り立つからです。(これは、(\(\bar{S}_i\) +$) \(>\)(\(\bar{S}_j\) +$) ならばそれぞれの末尾にどのような文字列を付け加えても辞書順が逆転しないことから従います。）
よって、\(S'\) の \(i\) 文字目が \(S_{K_i}\) の \(L_i\) 文字目に対応するという情報を用いて、求めたかった列 \(T\) を復元することができます。ここで、$ から 始まるsuffix は前に固まっており、これは空文字列に対応するので取り除いておきます。
また、\(\bar{S}_1, \ldots, \bar{S}_{|T|}\) についての LCP (Longest Common Prefix) 配列 \(LCP[i]\)も求めておきます。これは\(\bar{S}_i\) と \(\bar{S}_{i+1}\)のLCPの長さを表す配列であり、\(S'\) におけるLCP配列を \(\mathrm{LCP}_{S'}[i]\) として、 \(LCP[i]=\min(\mathrm{LCP}_{S'}[I+N],\min(|\bar{S}_i|, |\bar{S}_{i+1}|))\) で求める事ができます。(\(S'\) のSuffix array において最初の\(N\) 個は $ から始まる文字列であるため\(\mathrm{LCP}_{S'}[I]\) の添字 に \(N\) を加算している事に注意) 。また、便宜上 \(LCP[0]=LCP[|T|]=0\) とします。
2. 部分文字列の個数を辞書順で効率的に数える
次に、これらの情報から、部分文字列をどのように辞書順に並べられるかについて考えます。以降の部分については、ここで一度立ち止まり、自身で一度考えてから続きを読むことをお勧めします。
いま、部分文字列は \(\bar{S}_i\) のprefix 全体という形で与えられています。
ここで、\(i<j\) であるような \(i,j\) について、\(\bar{S}_i[1,R]\) と \(\bar{S}_j[1,R']\) を比較した時、\(\bar{S}_j[1,R']\) は \(\bar{S}_i[1,R]\) のprefix であるか、さもなくば \(\bar{S}_i[1,R]<\bar{S}_j[1,R']\) となります。よって、\(\bar{S}_i\) の prefix の集合に対して、辞書順である文字列 \(X\) 以下であるようなものの列挙が終わり、次に大きい文字列に対応する prefix を探すには次のようにすれば良いです。
ある \((i,R)\) \((1\leq i\leq |T|, 1\leq R\leq |S_i|)\) であって、次の \(3\) 条件をみたすものが( \(X\) より大きい部分列が存在する限り)一意に定まるため、それを取る。これは、\((i,R)\) \((1\leq i\leq |T|, 1\leq R\leq |S_i|)\) であってまだ選ばれていないもののうち整数の組として辞書順最小のものを選ぶと言い換える事もできます。
- 任意の \(1\leq j\leq i-1\), \(1\leq R'\leq |\bar{S_i}|\) について、\(\bar{S}_j[1,R']\leq X\)
- 任意の \(1\leq R'\leq R-1\) について\(\bar{S}_i[1,R']\leq X\)
- \(\bar{S}_i[1,R']> X\)
次の\(2\) 条件をみたす \(i\leq j\) をとる。 このとき、\(i\leq i' \leq j\) について \(\bar{S}_{i'}[1,R]=\bar{S}_i[1,R]\)であり、部分列のうち文字列と一致するものはそれらに限られます。
- \(i\leq i' <j\) について、 \(LCP[i']\geq R\)
- \(LCP[j]<R\) (\(LCP[|T|]=0\) として定義されている事に注意)
これを \(X\) が空文字列の状態から繰り返すことで、部分列としてあり得るすべての列およびそれらの個数を得る事ができます。 しかし、毎回これを求めようとすると、\(S_i\) の部分列としてあり得る文字列の個数分だけは少なくとも時間計算量がかかり、間に合いません。しかし、これは上の手順で選ばれる \((i,R,j)\) のうち \((i,j)\) に注目すると、\(i\) について昇順、さらにその中で \(j\) について降順となっており、まとめて計算するする事ができます。 この時、対応するような \(R\) が存在する \((i,j)\) は \(\max(LCP[i-1],LCP[j])<\min(LCP[i],\ldots,LCP[j-1])\)をみたしていなければならない事に注意すると、高々\(2|T|\) 個しかないことがわかります。 これは set などを用いて\(O(|T|\log |T|)\) で求める事が出来、 \(i\) を左から見ていき、対応する \(j\) としてあり得るものを stack 等を用いて管理して辞書順で後ろのものから埋めていく事によって、\(O(|T|)\) で実装する事ができます。
各 \((i,j)\) について、対応する \(R\) の値は\(a=\max(LCP[i-1],LCP[j])\), \(b=\min(LCP[i],\ldots,LCP[j-1])\)として、\(a<R\leq b\) の範囲全体と書けるため、対応する部分列は\((j-i+1)\times (b-a)\) 個あり、これを辞書順で見た時の個数として累積していき、\(x_i\) 番目のものがその中に存在するならば長さと \(T_i\) の 情報から答えを得る事ができます。
3. まとめ
以上をまとめると、
- \(S'\) を構築し、\(S'\) の Suffix Array および LCP を求める。 これを用いて、\(T\) および \(LCP[i]\) を求める。
- \(LCP[i]\) の情報を用いて、条件をみたす \((i,j)\) を走査し、\(T\) の情報をもとに答えを求める。
という順で答えを得る事ができます。1. は \(O\left(\displaystyle\sum_{i=1}^N \lvert S_i\rvert \right)\) で計算でき、2. はstack を用いる方針で \(O\left(Q+\displaystyle\sum_{i=1}^N \lvert S_i\rvert \right)\) で計算できるため、十分高速にこの問題を解く事ができました。
c++ による実装例:
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
int main() {
int n,q;
cin>>n;
vector<string> s(n);
for(int i=0;i<n;i++)cin>>s[i];
cin>>q;
vector<long long>x(q);
for(int i=0;i<q;i++)cin>>x[i];
vector<tuple<int,int,int> > ans(q);
//1.
int tot=0;
string str;
for(int i=0;i<n;i++){
str+=s[i]+'$';
tot+=s[i].size();
}
vector<int>rev(n+tot);
vector<pair<int,int> >t(tot);
vector<int>len(tot);
vector<int>lcp(tot+1);
vector<int> str_sa = suffix_array(str);
vector<int> str_lcp=lcp_array(str, str_sa);
for(int i=n;i<n+tot;i++)rev[str_sa[i]]=i-n;
int sz,cur=0;
long long m;
for(int i=0;i<n;i++){
sz=s[i].size();
for(int ii=0;ii<sz;ii++){
t[rev[cur+ii]]={i+1,ii+1};
len[rev[cur+ii]]=sz-ii;
}
cur+=sz+1;
m+=((long long)sz)*(sz+1)/2;
}
for(int i=1;i<tot;i++)lcp[i]=min(str_lcp[n+i-1],min(len[i-1],len[i]));
//2.
stack<int>j_cand;
int j,a,b,ans_len;
long long cnt;
cur=q-1;
for(int i=tot-1;i>=0;i--){
j_cand.push(i);
b=len[i];
while(!j_cand.empty()){
j=j_cand.top();
a=max(lcp[i],lcp[j+1]);
cnt=((long long)(j-i+1))*(b-a);
while(cur>=0){
if(x[cur]<=(m-cnt))break;
ans_len=(x[cur]+cnt-m-1)/(j-i+1)+1;
ans[cur]={t[i].first,t[i].second,t[i].second+a+ans_len-1};
cur--;
}
m-=cnt;
if(lcp[i]<=lcp[j+1])j_cand.pop();
if(lcp[i]>=lcp[j+1])break;
b=a;
}
}
for(int i=0;i<q;i++)cout<<get<0>(ans[i])<<" "<<get<1>(ans[i])<<" "<<get<2>(ans[i])<<"\n";
return 0;
}
posted:
last update: