# Poj Solution 3504

```http://poj.org/problem?id=3504

//* @author:alpc12
import java.util.*;

public class Main {
public static Scanner in=new Scanner(System.in).useLocale(Locale.US);

public void run() {
boolean[] singles=new boolean;
Map< String,String>[][] words=new Map;
for(int i=0;i< 26;++i) for(int j=0;j< 26;++j) words[i][j]=new HashMap< String,String>();
Set< String>[][] doublewords=new Set;
for(int i=0;i< 26;++i)
for(int j=0;j< 26;++j)
doublewords[i][j]=new HashSet< String>();
String s=in.next();
int n=in.nextInt();
for(int i=0;i< n;++i) {
String word=in.next();
if(word.length()==1) {
singles[word.charAt(0)-'a']=true;
} else {
int a=word.charAt(0)-'a',b=word.charAt(word.length()-1)-'a';
char[] letters=word.substring(1,1+word.length()-2).toCharArray();
Arrays.sort(letters);
if(words[a][b].containsKey(new String(letters)))
else words[a][b].put(new String(letters),word);
}
}
String[] prev=new String[s.length()+1];
int[] ways=new int[s.length()+1]; ways=1;
for(int i=0;i< s.length();++i) if(ways[i]>0) {
if(singles[s.charAt(i)-'a']) {
ways[i+1]=Math.min(2,ways[i+1]+ways[i]);
prev[i+1]=""+s.charAt(i);
}
for(int len=2;i+len<=s.length() && len<=100;++len) {
int a=s.charAt(i)-'a',b=s.charAt(i+len-1)-'a';
char[] letters=s.substring(i+1,i+1+len-2).toCharArray();
Arrays.sort(letters);
String word=new String(letters);
if(doublewords[a][b].contains(word))
ways[i+len]=Math.min(2,ways[i+len]+2*ways[i]);
else if(words[a][b].containsKey(word)) {
ways[i+len]=Math.min(2,ways[i+len]+ways[i]);
prev[i+len]=words[a][b].get(word);
}
}
}
if(ways[s.length()]==0) System.out.println("impossible");
else if(ways[s.length()]==2) System.out.println("ambiguous");
else {
List< String> ret=new ArrayList< String>();
Collections.reverse(ret);
for(int i=0;i< ret.size();++i) {
if(i!=0) System.out.print(" ");
System.out.print(ret.get(i));
}
System.out.println();
}

}

public static void main(String[] args) {
int n=in.nextInt();
for(int i=0;i< n;++i)
new Main().run();
}
}

```
This entry was posted in poj. Bookmark the permalink.