Hatena::Grouptopcoder

cou929のTopCoder日記

2009-05-01

SRM349 div2(過去問)

07:18

Easy - DocumentSearch

文字列をサーチする系統の問題。

この手の問題は、ループの境界を間違えやすいです。それぞれのループの開始・終了条件や、イテレータへの加減算には特に注意。逆にチャレンジのチャンスにもなる。

僕は今回、一致するフレーズがあるかどうかを自前で書いたのですが、関数(findとかsubstr)を積極的に使った方が、早いし安全ですね。

  int nonIntersecting(vector <string> doc, string search)
  {
    int i, j, k;
    int ret = 0;
    string s = "";

    for (i=0; i<doc.size(); i++)
      s += doc[i];

    for (i=0; i<s.size(); i++)
      {
	if (s[i] == search[0])
	  {
	    bool found = true;
	    for (k=1; k<search.size(); k++)
	      {
		if (s[i+k] != search[k])
		  {
		    found = false;
		    break;
		  }
	      }

	    if (i+search.size() > s.size())
	      found = false;

	    if (found)
	      {
		ret++;
		i += k-1;
	      }
	  }
      }

    return ret;
  }