Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2010-11-23SRM488(DIV1)

SRM488 第二問(500pt) TheBoringStoreDivOne

|  SRM488 第二問(500pt) TheBoringStoreDivOne - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM488 第二問(500pt) TheBoringStoreDivOne - hama_DU@TopCoderへの道

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

  • J、Bそれぞれ、2回以上出現する部分文字列をメモ。
  • その部分文字列をいくつか右(Bの場合は左)に伸ばしたパターンを全列挙。
    • substringやindexOf周りでバグったりした。
  • 全パターンゴリ押し。O(N^4)
  • 数時間かかって、他人のコードも参考にしながらやっと解けた。
    • systestで1.8sかかったケースもありかなりギリギリだった。(2秒以上だとタイムアップ)
    • div1の第2問を時間内に解くのは今の実力では難しい。方針はつかめるようになってきたけどね。

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map.Entry;

public class TheBoringStoreDivOne {
	public HashMap<String, HashSet<String>> jpattern = new HashMap<String, HashSet<String>>();
	public HashMap<String, HashSet<String>> bpattern = new HashMap<String, HashSet<String>>();

	public boolean isGreater(String a, String b) {
		if (a.length() > b.length() || (a.length() == b.length() && a.compareTo(b) < 0)) {
			return true;
		}
		return false;
	}

	public void addAllJ(HashMap<String, HashSet<String>> w, String pattern, String sub, int idx) {
		HashSet<String> list = null;
		if (!w.containsKey(pattern)) {
			list = new HashSet<String>();
		} else {
			list = w.get(pattern);
		}
		list.add("");

		String a = "";
		int from = idx + pattern.length();
		int to = sub.length();
		for (int i = from ; i < to ; i++) {
			a += sub.substring(i, i + 1);
			list.add(a);
		}
		w.put(pattern, list);
	}

	public void addAllB(HashMap<String, HashSet<String>> w, String pattern, String sub, int idx) {
		HashSet<String> list = null;
		if (!w.containsKey(pattern)) {
			list = new HashSet<String>();
		} else {
			list = w.get(pattern);
		}
		list.add("");

		String a = "";
		int from = idx - 1;
		int to = 0;
		for (int i = from ; i >= to ; i--) {
			a = sub.substring(i, i + 1) + a;
			list.add(a);
		}
		w.put(pattern, list);
	}

	public void jyunbi(String J, String B) {
		int j = J.length();
		int b = B.length();
		for (int x = 0 ; x < j ; x++) {
			for (int y = x + 1 ; y <= j ; y++) {
				String pattern = J.substring(x, y);
				String prefix = J.substring(0, x);
				String suffix = J.substring(y, j);


				int pre = prefix.indexOf(pattern);
				if (pre != -1) {
					do {
						addAllJ(jpattern, pattern, prefix, pre);
						pre = prefix.indexOf(pattern, pre+1);
					} while(pre != -1);
				}

				int suf = suffix.indexOf(pattern);
				if (suf != -1) {
					do {
						addAllJ(jpattern, pattern, suffix, suf);
						suf = suffix.indexOf(pattern, suf+1);
					} while(suf != -1);
				}
			}
		}

		for (int x = 0 ; x < b ; x++) {
			for (int y = x + 1 ; y <= b ; y++) {
				String pattern = B.substring(x, y);
				String prefix = B.substring(0, x);
				String suffix = B.substring(y, b);

				int pre = prefix.lastIndexOf(pattern);
				if (pre != -1) {
					do {
						addAllB(bpattern, pattern, prefix, pre);
						pre = prefix.lastIndexOf(pattern, pre-1);
					} while(pre != -1);
				}

				int suf = suffix.lastIndexOf(pattern);
				if (suf != -1) {
					do {
						addAllB(bpattern, pattern, suffix, suf);
						suf = suffix.lastIndexOf(pattern, suf-1);
					} while(suf != -1);
				}
			}
		}
	}

	public String find(String J, String B) {
		jyunbi(J, B);
		String answer = "";

		for (Entry<String, HashSet<String>> jp : jpattern.entrySet()) {
			for (String amarinJ : jp.getValue()) {
				for (Entry<String, HashSet<String>> bp : bpattern.entrySet()) {
					for (String amarinB : bp.getValue()) {
						if (amarinJ.equals(amarinB)) {
							String result = jp.getKey() + amarinJ + bp.getKey();
							if (isGreater(result, answer)) {
								answer = result;
							}
						}
					}
				}
			}
		}

		return answer;
	}
}