Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-02-29SRM392 (Practice)

SRM 392 TwoStringMasks

|  SRM 392 TwoStringMasks - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 392 TwoStringMasks - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=8706

コーディングフェーズ

  • 方針を検討
    • なんとなく前後に Z を追加しておく
    • 文字列を * で区切ると、
PPPPssss * SSSS
PPPP * pppSSSS
    • という形になるから、
      • *の前後部分(PPPP, SSSS)のそれぞれprefix と suffixが一致していなければ impossible としていいだろう
    • 問題は残った部分をどうするか・・・
      • 単純に PPPPsssspppSSSS としても正しいが、サンプルにもあるように最短でない場合がある
    • 文字列長は50と短いから、合わせる位置を全探索しちゃえばいいか
  • サンプル通った。
    • いくつかの追加ケースで確認
    • ・・・バグはなく、大丈夫そうだ。
    • 提出

システムテスト

  • 落ちる。なんで!?
    • ケースを見る。
PPPPssss * ppppSSSS
PPPP * SSSS
    • みたいなケースで落ちてた。つまり、ssss と ppppが同じ側にあるケース。
    • そのような場合は合わせることができないので、そのままつなげて返す。

public class TwoStringMasks {

	public String shortestCommon(String s1, String s2) {
		s1 = "Z" + s1 + "Z";
		s2 = "Z" + s2 + "Z";
		String[] d1 = s1.split("\\*");
		String[] d2 = s2.split("\\*");
		
		// front
		int mf = Math.min(d1[0].length(), d2[0].length());
		for (int i = 0 ; i < mf ; i++) {
			if (d1[0].charAt(i) != d2[0].charAt(i)) {
				return "impossible";
			}
		}
		String front = d1[0].substring(0, mf);
		boolean sone = true;
		String frontsuffix = "";
		if (d1[0].length() > d2[0].length()) {
			frontsuffix = d1[0].substring(mf);
		} else {
			frontsuffix = d2[0].substring(mf);
			sone = false;
		}
		
		int mmf = Math.min(d1[1].length(), d2[1].length());
		for (int i = 1 ; i <= mmf ; i++) {
			if (d1[1].charAt(d1[1].length()-i) != d2[1].charAt(d2[1].length()-i)) {
				return "impossible";
			}
		}
		String end = d1[1].substring(d1[1].length()-mmf);
		String endprefix = "";
		boolean eone = true;
		if (d1[1].length() > d2[1].length()) {
			endprefix = d1[1].substring(0, d1[1].length()-mmf);
		} else {
			endprefix = d2[1].substring(0, d2[1].length()-mmf);
			eone = false;
		}

		int fsl = frontsuffix.length();
		int epl = endprefix.length();
		int minpresuf = Math.min(fsl, epl);
		
		int maxsize = 0;
		if (sone ^ eone) {
			for (int m = 1 ; m <= minpresuf ; m++) {
				boolean isok = true;
				for (int i = 0 ; i < m ; i++) {
					if (frontsuffix.charAt(fsl-m+i) != endprefix.charAt(i)) {
						isok = false;
						break;
					}
				}
				if (isok) {
					maxsize = Math.max(maxsize, m);
				}
			}
		}
		
		String ans = front + frontsuffix + endprefix.substring(maxsize) + end;
		return ans.substring(1, ans.length()-1);
	}
}