AOJ2022

Princess, a Cryptanalyst

■問題
入力されたすべての文字列を部分文字列として含む最小の長さの文字列SSSを求める。
複数あったら辞書順で小さいものにする。

■解法
SSSの後ろの10文字と、使ったかどうかをビットで表現したやつを引数に持たせてDPする。
使うやつがSSSの後ろとかぶる場合は被らせたのも試して、SSSの中にもう含まれている文字列は使用済みということにして印を付ける。
また、引数が文字列なので多次元mapを使った。
DPしないとTLE、SSS全部もたせるとMLEする。
string.substr()をめちゃくちゃ使った。

■ソース

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <map>
using namespace std;
  
typedef pair<string,int> P;
  
int n;
string str[11];
string INF;
  
map<P,string> m;
 
int check(string s){
  int ret = 0;
  for(int i = 0; i < n; i++){
    if((int)s.find(str[i]) != -1){
      ret |= 1<<i; 
    }
  }
  return ret;
}
 
string solve(string sss,int used){
  if(m[P(sss,used)] != "") return m[P(sss,used)];
  
  if(used == (1<<n)-1) return "";
  
  string ret = INF;
  string temp = "";
  int c;
  
  for(int i = 0; i < n; i++){
    if( (used & 1<<i) == 0)
      for(int j = 1; j < (int)(min(sss.size(),str[i].size()));j++){
    if(sss.substr(sss.size() - j) == str[i].substr(0,j)){
 
      string t = sss + str[i].substr(j);
      c = check(t);
      temp = str[i].substr(j) + solve(t.substr(max((int)t.size()-10,0)),(used|1<<i)|c);
      if(ret.size() == temp.size()){
        ret = (ret < temp)?ret:temp;
      }else{
        ret = (ret.size() < temp.size())?ret:temp;
      }
    }
      }
 
      string t = sss + str[i];
      c = check(t);
      temp = str[i] + solve(t.substr(max((int)t.size()-10,0)),(used|1<<i)|c);   
      if(ret.size() == temp.size()){
    ret = (ret < temp)?ret:temp;
      }else{
    ret = (ret.size() < temp.size())?ret:temp;
      }
    }
  }
  return m[P(sss,used)] = ret;
}
  
int main(void)
{
  for(int i = 0;i < 111; i++) INF += "A";
  
  while(1){
    cin >> n;
    if(!n)break;
    for(int i = 0; i < n; i++){
      cin >> str[i];
    }
    map<P,string> a;
    m = a;
  
    cout << solve("",0) << endl;
  }
}