Dubious Document 2 [AtCoder Beginner Contest 076 C]

atcoder.jp

文字列 T が文字列 S の一部分と一致するかどうかを、S の全ての場所（S.length-T.length+1 箇所）で試します。

"?" を無視して一致を判定していき、もし T が S の一部分と一致するなら、S のその場所を T に、S に含まれる全ての "?" を "a" に変換してから、S を出力して終了です。

T が S のどの一部分とも一致しないなら、"UNRESTORABLE" を出力します。

ところで、条件には S は辞書順最小の文字列とあります。あっ、それなら "?" を全部 "a" にしてしまえばいいな、ということにはすぐに気が付いて、その通り書いて自信満々で提出したのですが、なかなか AC できません。なぜだろうと思い、自分で S と T を作って考えていたら、以下のようなテストケースに弾かれていたみたいです。

?????
z

私が書いたプログラムは、 S の先頭から T の一致を確かめていくものでした。ですので、このテストケースに対しては "zaaaa" と解答してしまいます。言うまでもなく、このテストケースの場合は "aaaaz" が正解です。S は辞書順最小ですから、前のほうにある "?" ほど "a" に置き換えるべきで、つまるところ T の位置はなるべく後ろのほうがよいわけです。

import java.util.*;

class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		
		char[] key = sc.next().toCharArray();
		char[] flagment = sc.next().toCharArray();
		int n = key.length - flagment.length;
		
		for (int i=n; i>=0; i--) { //Sの後方から探索
			
			boolean temp = true;
			for (int j=0; j<flagment.length; j++) {
				if (key[i+j]!='?' && key[i+j]!=flagment[j]) {
					temp = false;
					break;
				}
			}
			
			if (temp == true) {
				for (int j=0; j<flagment.length; j++) {
					key[i+j] = flagment[j];
				}
				for (int j=0; j<key.length; j++) {
					System.out.print(key[j]=='?' ? "a" : key[j]);
				}
				System.out.println();
				return;
			}
			
		}
		
		System.out.println("UNRESTORABLE");
		
	}
}

辞書順最小のものを……という問題に出会ったら、探索の方向に注意したいですね。