読者です 読者をやめる 読者になる 読者になる

SRM409 Div1Easy OrderedSuperString

問題文
ある文字列の部分文字列の配列が渡される。この時元の文字列の最小の長さを求めよ。
ただし各々の部分文字列は、それらの先頭の文字の座標が一つ前の部分文字列の座標以上の位置になっている。

解法
前の座標を記録しながら部分文字列の一致をみる。はじめは一致確認にfor文を使っていたが、string(iter, iter) を使っているコードがあったので自分もそちらを採用するに至った。

using namespace std;
class OrderedSuperString {
public:
  int getLength(vector <string> words) {
    string ret(words[0]);
    int F = 0;
    for(int i=1; i<words.size(); i++) {
      int N = ret.size();
      int M = words[i].size();
      bool ok = false;
      for(int j=F; j<N; j++) {
        int const len = min(N - j, M);
        if(string(ret.begin() + j, ret.begin() + j+len)
           == string(words[i].begin(), words[i].begin() + len)) {
          F = j;
          ok = true;
          ret += string(words[i].begin() + len, words[i].end());
          break;
        }
      }
      if(!ok) {
        F = N;
        ret += words[i];
      }
    }
    return (int)ret.size();
  }
};