2022 Princess, a Cryptanalyst

概要

10個以下の長さ10以下の文字列が与えられるので、それらの全てを部分文字列に含む最も短い文字列を求める。
複数ある場合は辞書順最小のものを。

方針

すでに他の文字列の部分文字列になっているものは省いてから、つなぎ方を全探索する。
このとき、二つの文字列を繋いだ時の重なる文字数をあらかじめ計算しておく。
next_permutation遅い。。。

ソース

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;

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

int table[15][15];

int dup(string s,string t) {
  int i,k = min(s.length(), t.length());
  for(int i=k; i>=0; --i)
    if(s.substr(s.length()-i) == t.substr(0,i)) return i;
  return 0;
}

string conc(vector<int> &perm,vector<string> &input) {
  string res = input[perm[0]];
  for(int i=0; i<perm.size()-1; ++i) {
    res += input[perm[i+1]].substr(table[perm[i]][perm[i+1]]);
  }
  return res;
}

bool issubstr(string s,string t) {
  if(s.length() > t.length()) return false;
  for(int i=0; i<t.length()-s.length(); ++i) {
    if(t.substr(i,s.length()) == s) return true;
  }
  return false;
}

int main() {
  int i,j,k,tt,n;
  while(cin>>n, n) {
    memset(table,0, sizeof(table));

    vector<string> input(n),tmp;
    vector<int> dd;
    rep(i,n) cin>>input[i];

    rep(i,n) rep(j,n) if(issubstr(input[i],input[j])) dd.push_back(i);

    rep(i,n)
      if(find(dd.begin(), dd.end(), i) == dd.end()) tmp.push_back(input[i]);
    input.clear();
    rep(i,tmp.size()) input.push_back(tmp[i]);
    rep(i,input.size()) rep(j,input.size()) table[i][j] = dup(input[i],input[j]);

    vector<int> perm;
    int total = 0,ansl = 1<<29;
    rep(i,input.size()) {
      perm.push_back(i);
      total += input[i].length();
    }

    string ans = "";
    do{
      tt = 0;
      rep(i,input.size()-1) {
	tt += table[perm[i]][perm[i+1]];
      }

      if(ansl > total-tt) {
	ansl = total-tt;
	ans = conc(perm,input);
      }else if(ansl == total-tt) {
	string t = conc(perm,input);
	if(ans > t) ans = t;
      }
    }while(next_permutation(perm.begin(), perm.end()));

    cout<<ans<<endl;
  }
}