indexが昇順になるように文字列を連結していってその長さを答える

最初はindexを増やしていきながらマッチする文字列領域を決めていくという流れでコードを書いたのだけどそれだとシステムテストが通せなかったので、あきらめた。

{"aaaaaaaaaa", "a", "ab", "a", "abbbb"}

が14でなくて16になってしまう。

結局マージしたい文字列がsuperstringに含まれるかfindして、見つかればインデックスを書き換えて次の文字をマージしていく。含まれない場合はオーバーラップしている部分を一文字ずつ減らしながら探っていく方法に変えた。

class OrderedSuperString {
public:
  int getLength(vector <string> words) {
    string superstring = words[0];
    int ind = 0;
    if(words.size() == 1) return superstring.length();

    for(int i=1;i<words.size();++i){
      int matched = superstring.find(words[i],ind);
      if(matched != string::npos){ 
        ind = matched; continue;
      }

      int overlapped; 
      for(overlapped=min(superstring.length()-ind,words[i].length());overlapped>0;--overlapped){
        if(superstring.substr(superstring.length()-overlapped,overlapped) == words[i].substr(0,overlapped)) break;
      }
      ind = superstring.length()-overlapped;
      superstring += words[i].substr(overlapped,words[i].length()-overlapped);
    }
    return superstring.length();
  }
};