解いた問題

5/31/2012

SRM409 Div2 Medium

500

やるだけ



string f(string a, string b, int &idx)
{
  if (a.size() < b.size()) {
    for (int i = idx; i < (int)a.size(); ++i) {
      string p = a.substr(i);
      string q = b.substr(0, a.size() - i);
      if (p == q) {
        idx = i;
        return a + b.substr(a.size() - i);
      }
    }
  } else {
    for (int i = idx; i < (int)a.size(); ++i) {
      int mn = min(a.size() - i, b.size());
      string p = a.substr(i, mn);
      string q = b.substr(0, mn);
      if (p == q) {
        idx = i;
        return a + b.substr(mn);
      }
    }
  }
  idx = a.size();
  return a + b;
}

class OrderedSuperString {
public:
  int getLength(vector <string> ws)
  {
    int idx = 0;
    for (int i = 1; i < (int)ws.size(); ++i) {
      ws[i] = f(ws[i - 1], ws[i], idx);
    }

    return ws.back().size();
  }
};