SRM 579 Div2 Medium UndoHistory

問題

SRM 579 - TopCoder Wiki

undo機能付きテキストエディタで与えられた入力を出力するのにかかる最小コストを求める問題． - バッファがあり，バッファに1文字タイプするのに手数１． - エンターキーを押して画面に出力するのに手数１． - 過去にバッファに入力された全ての文字列をhistoryに記録しておいて，その中の文字列をバッファに出力するのに手数２． - エンターをおした時バッファはクリアされない

解答

• バッファにタイプする前に，以前のhistoryと一致する最長文字列を計算しバッファに出力する．
• 最初の場合と，一つ前のlineが今のlineの真のprefixの時はどっちがコストが低いか考える．

using namespace std;


class UndoHistory
{
public:
  int minPresses(vector <string> lines)
    {
      set<string> tree;
      int n = lines.size();
      int i, j, k;
      int res = 0;
      set<string>::iterator itr;
      for(i = 0; i < n; i++){
        // cout << "i=" << i << " res=" << res << endl;
        int m = lines[i].size();
        j = 0;
        int max_len = 0;
        bool previous = false;
        if (i > 0
            && lines[i].size() >= lines[i-1].size()
            && lines[i].substr(0,lines[i-1].size()) == lines[i-1]){
          previous = true;
        }
        for (k = m; k > 0; k--){
          itr = tree.find(lines[i].substr(0, k));
          if (itr != tree.end()){
            max_len = k;
            break;
          }
        }
        size_t vv = lines[i].size() * 10;
        if (i == 0) {
          vv = lines[i].size();
        }
        vv = min(vv, 2 + lines[i].size() - max_len);
        if (previous) vv = min(vv, lines[i].size() - lines[i-1].size());
        res += vv;
        for(j = 0; j < m; j++) tree.insert(lines[i].substr(0, j+1));
        res++;
      }
      return res;
    }
};