TopCoder SRM349 Div2 250Pts

このTopCoderの問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。問題についておおまかに説明する。

あなたは文書をスキャンして、何回特定の単語・フレーズが現れたかをカウントする関数を書く仕事を与えられた。しかし
オーバーラップして出現回数を数えないということが重要である。例えば"abababa"という文字列で"ababa"というキーワードの出現回数を数えるとき、添え字0からと添え字2からの2つがあるが、重なっているので両方を数えることはしてはならない。また、docという文字列型配列を1つの文字列に結合しなければならない。そして、searchという文字列が重ならないという条件で最大でいくつ登場するかを数えて返せ。

私の解答はこちら。

public class DocumentSearch {

 public int nonIntersecting(String[] doc, String search) {
  StringBuilder sb = new StringBuilder();
  for( int i=0 ; i<doc.length ; i++ ){
   sb.append(doc[i]); // 文字列の結合
  }
  String docs = sb.toString();
  int n = 0;
  int len = search.length();
  while( true ){
   int idx = docs.indexOf(search); // 初めてsearchが現れる位置を探索
   if( idx < 0 ) break;
   n++;
   // docsを更新してsearchの最後の文字以前を取り除く
   docs = docs.substring(idx+len);
  }
  return n;
 }

}

得点は240.75/250、中央値は約192点。1回のsubmitでシステムテストクリア。コード中で利用しているStrignクラスのメソッドindexOfにはfromIndexという引数をとる方法がある。これにより、文字列の途中から探索できるので、docsの更新は不要になる。オブジェクトの繰り返し生成を避ける際に有効になるでしょう。