LiveArchive 4994 Overlapping Scenes

解法
入力の文字列を next_permutation() して、順に重ねあわせていく。２つの文字列に対して重ね合わせをして、末尾文字列から一致した部分を引いたものを返す関数 concat() を用意した。

#include <bits/stdc++.h>

using namespace std;

#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define chmin(a,x) a=min(a,x)

int const INF = 1<<29;

string concat(string const& now, string const& suffix) {
  
  int const now_len = now.size();
  int const suf_len = suffix.size();
  
  int clen = -1;
  rep(i, now_len) {
    rep(j, suf_len) {
      if(now[i+j] != suffix[j]) { break; }
      if(i+j >= now_len-1) { clen = j+1; goto OK; }
    }
  }

  return suffix;
  
 OK:;
  return suffix.substr(clen);
  
}

int main() {
  
  int Tc; cin >> Tc;
  rep(tc, Tc) {
    int N; cin >> N;
    
    cout << "Case " << tc + 1 << ": ";
    
    string strs[N];
    rep(i, N) cin >> strs[i];
    sort(strs, strs+N);
    
    int mnlen = INF;
    do {
      string now;
      rep(i, N) {
        now += concat(now, strs[i]);
      }
      chmin(mnlen, (int)now.size());
    } while(next_permutation(strs, strs+N));
    
    cout << mnlen << endl;
  }
  
  return 0;
}