naoya_t@topcoder

SRM409 Div1 Easy: OrderedSuperString

過去問, 練習 | 18:07 |

酩酊状態で解いたら１時間かかった。バグっててシステムテスト１つ通らず。（→直った）

class OrderedSuperString {
public:
  int getLength(vector<string> words) {
    int n=words.size();

    string w0=words[0];
    int l0=w0.length();
    if(n==1) return l0;
    int a0=0;

    for (int i=1;i<n;i++) {
      string wi=words[i];
      int li=wi.length();
      if (l0>=li) {
        for(int a=a0;a<=l0-li;a++) {
          if(w0.substr(a,li)==wi) {a0=a; goto next;}
        }
      }
      for(int w=min(l0,li-1);w>0;w--){
        if(l0-w<a0)continue;
        if (w0.substr(l0-w,w)==wi.substr(0,w)) {w0+=wi.substr(w,li-w);a0=l0-w;l0+=li-w;goto next;}
      }
      a0 = l0; w0 += wi; l0 += li;
    next:
      ; 
    }
    return l0;
  }
};