/* * ACM ICPC - CERC 2011 * * Sample solution: Vigenere Cipher Analysis (analyse) * Author: Martin Kacer */ import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.HashSet; import java.util.Set; import java.util.StringTokenizer; public class analyse { StringTokenizer st = new StringTokenizer(""); BufferedReader input = new BufferedReader(new InputStreamReader(System.in)); public static void main(String[] args) throws Exception { analyse instance = new analyse(); while (instance.run()) {/*repeat*/} } String nextToken() throws Exception { while (!st.hasMoreTokens()) st = new StringTokenizer(input.readLine()); return st.nextToken(); } int nextInt() throws Exception { return Integer.parseInt(nextToken()); } String sumString(String key, CharSequence txt, int start, int end, boolean plus) { if (end == -1) end = txt.length(); StringBuilder sb = new StringBuilder(); for (int i = start; i < end; ++i) { int offs = key.charAt((i-start) % key.length()) - 'A' + 1; if (!plus) offs = -offs; char c = (char)(txt.charAt(i) + offs); sb.append((c < 'A') ? (char)(c+26) : (c > 'Z') ? (char)(c-26) : c); } return sb.toString(); } int maxKeyLen; Set posKeys1 = new HashSet(100000), posKeys2 = new HashSet(10000); boolean isRepetition(String key, int len) { for (int i = len; i < key.length(); ++i) if (key.charAt(i) != key.charAt(i-len)) return false; return true; } /** We are lazy, so instead of avoiding overlap at all, we detect it here. */ boolean containsBoth(String txt, String s1, String s2) { for (int i1 = txt.indexOf(s1); i1 >=0; i1 = txt.indexOf(s1, i1+1)) for (int i2 = txt.indexOf(s2); i2 >=0; i2 = txt.indexOf(s2, i2+1)) { if (i2 >= i1 + s1.length() || i1 >= i2 + s2.length()) return true; } return false; } boolean run() throws Exception { maxKeyLen = nextInt(); if (maxKeyLen == 0) return false; posKeys1.clear(); posKeys2.clear(); String s1 = nextToken(), s2 = nextToken(), msg = nextToken(); for (int start = 0; start <= msg.length() - s1.length(); ++start) { String key = sumString(s1, msg, start, start+s1.length(), false); for (int i = 1; i <= maxKeyLen; ++i) if (isRepetition(key, i)) { String k = (i == key.length()) ? key : key.substring(0, i); int idx = i - start%i; if (idx < i) k = k.substring(idx) + k.substring(0, idx); posKeys1.add(k); } } for (int start = 0; start <= msg.length() - s2.length(); ++start) { String key = sumString(s2, msg, start, start+s2.length(), false); for (int i = 1; i <= maxKeyLen; ++i) if (isRepetition(key, i)) { String k = (i == key.length()) ? key : key.substring(0, i); int idx = i - start%i; if (idx < i) k = k.substring(idx) + k.substring(0, idx); //System.err.println("DBG2: " + key + "/" + i + "->" + k); if (posKeys1.contains(k)) posKeys2.add(k); } } //System.err.println("1: " + posKeys1); System.err.println("2: " + posKeys2); String restxt = null; for (String k : posKeys2) { String txt = sumString(k, msg, 0, -1, false); if (containsBoth(txt, s1, s2)) { if (restxt != null && !restxt.equals(txt)) { System.out.println("ambiguous"); return true; } else restxt = txt; } } System.out.println((restxt == null) ? "impossible" : restxt); return true; } }