minl.cc

#include <string>
#include <vector>
#include <iostream>

using namespace std;

typedef vector<string> strings;
const int INF = (1 << 11);

template<class T>
ostream& operator<<(ostream& os, vector<T> v) {
  os << "(\"" << v[0] << "\"";
  for (int i=1, len=v.size(); i<len; ++i) os << " \"" << v[i] << "\"";
  os << ')';
  return os;
}

string shortest_one(strings&S) {
  string r = "";
  int mx = INF;
  for (string&s : S) {
    int n = s.size();
    if (mx > n) {
      mx = n;
      r = s;
    }
  }
  return r;
}

template <typename T>
vector<T> subvector(vector<T>&v, int begin = 0, int end = -1) {
  vector<T> r;
  if (begin == end) return r;
  int I = v.size();
  for (int i = begin; i < I && i < end; ++i) {
    r.push_back(v[i]);
  }
  return r;
}

bool string_include(string str, strings&sigma) {
  int idx = 0;
  for (string s : sigma) {
    idx = str.find(s, idx);
    if (idx == string::npos) {
      return false;
    }
    idx += s.size();
  }
  return true;
}

bool language_include(strings&S, strings&sigma) {
  for (string s : S) {
    if (! string_include(s, sigma)) return false;
  }
  return true;
}

strings append(strings a, string s, strings b) {
  strings r;
  for (string s : a) r.push_back(s);
  r.push_back(s);
  for (string s : b) r.push_back(s);
  return r;
}

strings minl(strings&S) {
  string s = shortest_one(S);
  strings sigma = {};
  int n = s.size();
  int m = 0;

  while (n > 0) {
    for (int i = 0; i == 0 || i < s.size() - n + 1; ++i) {
more:;
      for (int j = 0; j == 0 || j < m + 1; ++j) {
        strings sigma2 =
          append(subvector(sigma, 0, j),
                 s.substr(i, n),
                 subvector(sigma, j, m));

        if (language_include(S, sigma2)) {
          sigma = sigma2;
          m = sigma2.size();
          goto more;
        }
      }
    }
    n = min<int>(s.size() - sigma.size(), n - 1);
  }

  return sigma;
}

int main() {

  strings S = {
    "This is a cat",
    "That is the cat",
    "This is not a dog"
  };

  cout << minl(S) << endl;

  return 0;
}