Single Round Match 409 Div2 500pt

http://www.topcoder.com/stat?c=problem_statement&pm=9823&rd=12181&rm=297980&cr=22724714
問題を簡単に解説すると「文字列をたくさん渡すので、それをつなぎ合わせた大きな文字列を作ってください。ただし、なるべく小さく、おのおのの部分文字列の位置が与えられた順になっているように。たとえばabとbaが渡されたらabbaはダメでabaが正解。aabとbaaならaabaaが正解で、baabは順番が与えられた順と違うのでダメ。出来上がった文字列の長さを返してください。」というもの。

つまったところは今回初めて使ったstringのfindメソッド。見つからなかったときに-1を返すのかと思いきや、帰り値がunsigned intだという。

  unsigned int fpos = last.find(cur, 0);
  if(fpos == 4294967295U){ // not found

一日置いてしまうとアルゴリズムを説明しにくいなぁ。ようするに直前の文字列の頭以降の文字列(string &last)を持っておいて、そこからfindで見つかるならそこに重ねる。見つからなかった場合は可能な限り重ねてみて、重ならなかったらすこし重なりを減らして、をくりかえして一番大きく重なるのを探す。もちろん一番大きく重なるのが一番短くなる重ね方だからね。で、その位置以降をlastにして最後まで繰り返す。

Pythonic sliceって書いてある関数は前に作った物のコピペ。いまはtoolbox.cppっていうたくさんの関数の入っているファイルから、必要な物だけをコピペして使っているけど、使われている物だけを自動的にソースコードに埋め込むスクリプトって作れるだろうか。
つくれるなら「#include "toolbox.cpp"とかやっておいて、完成してからその埋め込みスクリプトを走らせて必要な物だけ埋め込んでからsubmit」なんてのができるはずだよなぁ。一度includeを削って実行して「tmp.cpp:126: error: ‘foo’ was not declared in this scope」とか表示されるのを使って使われている物を特定すればいいんだろうか。

// Pythonic slice
string slice(string s, int start, int end){
  if(end <= 0) end += s.size();
  if(start < 0) start += s.size();
  return s.substr(start, end - start);
}
string slice(string s, int start){
  return slice(s, start, 0);
}

class OrderedSuperString {
public:
  int getLength(vector <string> words) {
    int result = 0;
    result += words[0].size();
    string &last = words[0];
    size_t N = words.size();
    for(size_t i=1; i<N; i++){
      string &cur = words[i];
      unsigned int fpos = last.find(cur, 0);
      if(fpos == 4294967295U){ // not found
	//cout << "not found" << endl;
	int maxcover = min(last.size(), cur.size());
	int cover = maxcover;
	for(; cover >= 0; cover--){
	  if(cover == 0) break;
	  if(slice(last, -cover) == slice(cur, 0, cover)){
	    //cout << last << "&" << cur << " overwrap: " << cover << endl;
	    break;
	  }
	}
	//cout << "cover" << cover << endl;
	last = cur;
	result += cur.size() - cover;
	//cout << "result: " << result  << endl;
	
      }else{
	//cout << "found" << endl;
	uint rest = last.size() - fpos;
	if(rest < cur.size()){
	  result += cur.size() - rest;
	}
	last = slice(last, fpos);
	//cout << "result: " << result  << endl;
      }
    }
    return result;
  }