TopCoder SRM254 Div2 500Pts

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

多人数協力型のオンラインゲームを作っている。チームのプレーヤーはゲームの間互いにチャットができ、敵を作るAIを作成するときに、その会話を利用したいと思っている。AIの機能には、与えられたフレーズがプレーヤーのチャットの一部であるか判断するということが含まれている。もちろん、さまざまなフレーズが与えられるのだが、できるだけそれを見つけ出したいと思っている。フレーズに使われるのは、簡略表記が最も一般的であろう。例えば、cptrというのはcaptureという言葉の略である。さて、問題ではtypedというプレーヤーがタイプした文字列と、それに対しチェックしたいphraseという文字列が与えられる。phraseからtypedの文字を取り除いた結果を返せ。もし、phraseからtypedを単に除いた文字列が得られないようであれば、"UNMATCHED"を返せ。なお、この制約により、返す文字列は唯一に定まる。

私の解答はこちら。

public class ListeningIn {

 public String probableMatch(String typed, String phrase) {
  StringBuilder sb = new StringBuilder();
  int nStart = 0;
  int nPrev = 0;
  for( int i=0 ; i<typed.length() ; i++ ){
   String aTyped = typed.substring(i, i+1);
   if( nPrev > phrase.length()-1 ){
    // まだ検討しなければならない文字が残っているのに、終端まで来てしまった
    return "UNMATCHED";
   }
   for( int j=nStart ; j<phrase.length() ; j++ ){ // 直前の文字の次からスタート
    if( phrase.substring(j, j+1).equals(aTyped) ){ // 探したい文字があった
     nStart = j+1; // 次の開始位置
     break;
    }
   }
   if( nPrev == nStart ) return "UNMATCHED"; // 次の開始位置が見つからなかった
   // typedに現れた2文字の間を解答を格納する変数に入れる
   sb.append(phrase.substring(nPrev, nStart-1));
   nPrev = nStart; // 次の開始位置は直前の開始位置になる
  }
  sb.append(phrase.substring(nPrev));
  String ret = sb.toString();
  return ret;
 }

}

typedの先頭から順に何番目の文字と一致するかということを調べて、次の文字からは先頭の位置から順に後方に現れ、phraseの一番後ろに行くまでにtypedがすべて現れればOKというのが方針。実装するに当たり、空白は飛ばすなど要求と異なる実装をしていたので、かなり時間がかかってしまいました。