LCPに関する問題．先頭から貪欲に考えるのが基本．Binary Trie に近い．
とりあえず，\(n\) 個は多いので 2つで考える． 2つの文字列 \(s,t \) の LCP は，先頭から貪欲に調べれば求まる．
次に複数の文字列を同時に判定することを考える． これは tree を再帰的に見ていき，類別していくことで実現できる． Tree の葉に向かうにつれて，類が増えていき，細かく分解される．
より正確には，次の様に説明できる．深さ \(d\) とする． \(i, j \in n\) に対して， \(s_{i} \sim s_{j}\)を \(s_{i}\) と \(s_{j}\) の先頭 \(d\) 文字が等しいとき と定める．これは同値関係になる． \(cs_{d} := \{0, 1, \cdots, n-1\} / \sim \) とおく． 任意の \(d\) と 任意の \(c \in cs_{d+1} \)に対して， ある \(c' \in cs_{d}\) が存在して， \(c \subset c'\).
\(c'\) の分解の中に \(c\) が現れるということであり， それは \(i \in c'\) に対して \(s_{i}\) の \(d\) 文字目で類別すればよい．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n, m, k, q;
cin >> n;
cinv(s);
vvll v;
vll ans(n, -1);
auto f = [&](auto f, ll k = 0) -> void {
vvll nv;
// k : depth
for(auto c:v){
vvll tmp(26);
for(ll j: c){
if(k < s[j].length()) tmp[s[j][k]-'a'].push_back(j);
else ans[j] = k;
}
rep(i,26) if(tmp[i].size()){
if(tmp[i].size() == 1){
ll j = tmp[i].front();
ans[j] = k;
}else{
nv.push_back(tmp[i]);
}
}
}
swap(nv, v);
if(nv.size()) f(f, k+1);
};
vll tmp; rep(i,n) tmp.push_back(i);
v.push_back(tmp);
f(f);
rep(i,n){
cout << ans[i] << endl;
}
return 0;
}
