問題原案: physics0523

この解説では、文字列 \(s,t\) をこの順に連結した文字列を \(st\) と書くことにします。

---

もしこの問題が以下のようであれば、これは有名問題です。

\(N\) 個の文字列 \(S_i\) が与えられる。
\(S_i\) を好きな順で連結した時、できる文字列のうち辞書順最小であるものを求めよ。

ECR9-C はまさにこの問題であり ( 解説 参考 )、 ABC225-F もこの問題の類題です ( 解説 )。

まずこの問題の解法を述べることから始めましょう。

上記の問題は、次のようにして解くことができます。

文字列を以下で定義した順序でソートした後、並べ替え後の順番で連結することで最適な文字列が得られる。

• \(XY<YX\) である、またその時に限り、 \(X<Y\) と順序付ける。

証明は上記の問題の解説を参照してください。

ただし、今回の制約 ( \(N \le 3 \times 10^5, \Sigma |S_i| \le 10^6\) ) ではここに落とし穴があります。 ( 以下の指摘は作問過程で Nyaan さんに行って頂きました。 )

比較の際、愚直に \(XY,YX\) を作成して比較した場合、比較の実行に \(O(|X|+|Y|)\) かかってしまいます。
ソートの際に特定の文字列 \(S_i\) を \(O(N)\) 回参照してしまうと、時間計算量が \(\Omega(N |S_i|)\) となり、 \(|S_i|\) が大きい時に TLE してしまいます。
これを回避する解法も存在します。こちらから続きをお読みください。
同じ理由から、比較に \(O(\max(|X|,|Y|))\) かけることも許されません。

しかし、もし比較を \(O(\min(|X|,|Y|))\) で行うことが出来れば、全体で \(O(\Sigma |S_i| \log N)\) でのソートを実行することが出来ます。

\(XY < YX\) かどうかの判定を \(O(\min(|X|,|Y|))\) で行うにはどうすればよいでしょうか?

文字列 \(X\) とともに \(X\) の Z-array (Z-algorithm を適用した結果) である \(Z_X\) とを保持しておけばよいです。

\(|X| \ge |Y|\) の場合の比較方法を示します。 ( \(|X| < |Y|\) についても同様の比較ができます。)

• \(XY\) を \(X[1,|Y|] X[|Y|+1,|X|], Y\) 、 \(YX\) を \(Y X[1,|X|-|Y|], X[|X|-|Y|+1,|X|]\) と捉える。
• まず、 \(X[1,|Y|]\) と \(Y\) とを先頭の文字から順に比較する。
• ここまでで結果が決まらない場合、 \(X[|Y|+1,|X|]\) と \(X[1,|X|-|Y|]\) との比較になる。
  • この比較を \(Z_X\) を利用して \(O(1)\) で行う。
  • \(Z_X[|Y|+1] \ge |X|-|Y|\) であるとき、両者は等しいことが分かるので次に進む。
  • そうでないとき、両者の \(Z_X[|Y|+1] +1\) 文字目は異なるので、その文字を調べると大小関係が判明します。
• ここまでで結果が決まらない場合、 \(Y\) と \(X[|X|-|Y|+1,|X|]\) とを先頭の文字から順に比較する。

---

この順序で文字列を並び替えた結果を \(S'_1,S'_2,\dots,S'_N\) とします。ここからこの問題の答えを求めましょう。

• \(N=2\) であれば、 \(S'_2S'_1\) が答えである。
• ある整数 \(1 \le i < N\) であって、 \(S'_i S'_{i+1}=S'_{i+1}S'_i\) なるものが存在するなら、 \(S'_i\) と \(S'_{i+1}\) を swap することでも同じ文字列が得られるので、 \(S'\) の各文字列を順に連結したものが答えである。
• ここまでで求解できていないケースについて、以下が満たされる。
  • どのような整数 \(1 \le i < N\) についても、 \(S'_iS'_{i+1}\) と \(S'_{i+1}S'_i\) が異なる。
• 実は、答えは以下のうち辞書順で小さい方である。
  • \(S'_1S'_2 \dots S'_{N}S'_{N-1}\)
  • \(S'_1S'_2 \dots S'_{N-1}S'_{N-2}S'_N\)

最後の事実を証明します。
まず、 \(S'\) から転倒数 \(2\) 以上ある順序で連結した文字列は解となりえません。
これは、転倒数を減らす度に辞書順でより小さい文字列が得られる ( つまり、転倒数 \(2\) 以上の場合は自身より辞書順で小さい文字列が \(2\) つ以上存在する ) からです。

次に、 \(S'_1S'_2 \dots S'_{N-1}S'_N\) 、 \(S'_1S'_2 \dots S'_{N}S'_{N-1}\) という \(2\) つの文字列が存在します。
このことから、接頭辞が \(S'_1S'_2 \dots S'_{N-2}\) でない文字列は解となりえません。
どのような整数 \(1 \le i < N\) についても、 \(S'_iS'_{i+1}\) と \(S'_{i+1}S'_i\) が異なることから、転倒数 \(1\) の中でも \(S'_{N-2}\) 以前の文字列間の swap は解となりえません。
こうして残るのが以下の \(2\) つの候補です。

• \(S'_1S'_2 \dots S'_{N}S'_{N-1}\)
• \(S'_1S'_2 \dots S'_{N-1}S'_{N-2}S'_N\)

例えば \(S'=(\) a, b, c \()\) であるとき前者が、 \(S'=(\) a, aab, b \()\) であるとき後者が最適解となります。

あとはこれを実装すればこの問題に正解できます。

文字列のソートは \(O(\Sigma |S_i| \log N)\) で実現可能です。
\(S'_i S'_{i+1}=S'_{i+1}S'_i\) なる \(i\) の存在性の判定は愚直に実装しても時間計算量 \(O(\Sigma |S_i|)\) です。
最後のステップの \(2\) つの候補間の比較も \(O(\Sigma |S_i|)\) です。
こうして、この問題全体を時間計算量 \(O(\Sigma |S_i| \log N)\) で解くことが出来ました。

実装例 (C++):

#include<bits/stdc++.h>
#include<atcoder/string>

using namespace std;
using namespace atcoder;

using psv=pair<string,vector<int>>;

bool comp(const psv &x,const psv &y){
  int xl=x.first.size(),yl=y.first.size();
  if(xl>=yl){
    for(int i=0;i<yl;i++){
      if(x.first[i] != y.first[i]){
        return (x.first[i] < y.first[i]);
      }
    }

    if(xl!=yl && x.second[yl]<(xl-yl)){
      return (x.first[yl+x.second[yl]]<x.first[x.second[yl]]);
    }

    for(int i=0;i<yl;i++){
      if(y.first[i] != x.first[i+(xl-yl)]){
        return (y.first[i] < x.first[i+(xl-yl)]);
      }
    }
  }
  else{
    for(int i=0;i<xl;i++){
      if(x.first[i] != y.first[i]){
        return (x.first[i] < y.first[i]);
      }
    }

    if(y.second[xl]<(yl-xl)){
      return (y.first[y.second[xl]]<y.first[xl+y.second[xl]]);
    }

    for(int i=0;i<xl;i++){
      if(y.first[i+(yl-xl)] != x.first[i]){
        return (y.first[i+(yl-xl)] < x.first[i]);
      }
    }
  }
  return false;
}

string concat(vector<psv> &s){
  string res="";
  for(auto &nx : s){ res+=nx.first; }
  return res;
}

int main(){
  int t;
  cin >> t;
  while(t--){
    int n;
    cin >> n;
    vector<psv> s(n);
    for(auto &nx : s){
      cin >> nx.first;
      nx.second=z_algorithm(nx.first);
    }
    sort(s.begin(),s.end(),comp);

    if(n==2){
      cout << s[1].first+s[0].first << "\n";
      continue;
    }
    
    bool ok=false;
    for(int i=1;i<n;i++){
      if(s[i-1].first+s[i].first == s[i].first+s[i-1].first){ok=true; break;}
    }
    if(ok){
      cout << concat(s) << "\n";
      continue;
    }

    swap(s[n-1],s[n-2]);
    string c1=concat(s);
    swap(s[n-1],s[n-2]);
    swap(s[n-2],s[n-3]);
    cout << min(c1,concat(s)) << "\n";
  }
  return 0;
}