String preProcess(String s) {
		// convert abc to ^#a#b#c#$
		int n = s.length();
		if (n == 0)
			return "^$";
		StringBuilder ret = new StringBuilder();
		ret.append("^");
		for (int i = 0; i < n; i++)
			ret.append("#").append(s.substring(i, i + 1));

		ret.append("#$");
		return ret.toString();
	}