3093707_wa.java

北大大牛代码 1240道题的原代码 超级权威

import java.util.*;

public class Main
{
	public static void main(String [] args)
	{
		new Main().solve();
	}

	private void solve()
	{
		Scanner cin = new Scanner (System.in);
		int cas, i, j, n;
		String mes;
		String [] dic = new String [10002];
		String [] tmp = new String [10002];
                char [] str = new char [102];
                int [] pos = new int [256];
                int [] end = new int [256];
                int [] length = new int [10002];

		cas = cin.nextInt();
		while(cas-- > 0)
		{
			mes = cin.next();
			n = cin.nextInt();
			for(i = 0; i < n; i++)
			{
				dic[i] = cin.next();
				
			}
                        Arrays.sort(dic,0,n,new Comparator()
                        {
                            public int compare(Object o1,Object o2)
                            {
                                String a = (String) o1;
                                String b = (String) o2;
                                
                                if(a.charAt(0)==b.charAt(0))
                                    return a.length() - b.length();
                                else
                                    return a.charAt(0)-b.charAt(0);
                            }
                        });
                        for(i = n-1; i >= 0; i--)
                        {
                            pos[dic[i].charAt(0)] = i;
                        }
                        for(i = 0; i < n; i++)
                        {
                            length[i] = dic[i].length();
                            str = dic[i].toCharArray();
                            Arrays.sort(str);
                            tmp[i] = new String(str);
                            end[dic[i].charAt(0)] = i;
                        }
                        int [] cnt = new int [10002];
                        int [] prev = new int [10002];
                        int len = mes.length();
                        cnt[1] = 1;
                        for(i = 0; i < len; i++)
                        {
                            if(cnt[i+1]==0)
                            {
                                continue;
                            }
                            for(j = pos[mes.charAt(i)]; j <= end[mes.charAt(i)]; j++)
                            {
                                int l = i + length[j];
                                if(l > len)
                                {
                                    break;
                                }
                                if(mes.charAt(l-1)!=dic[j].charAt(length[j]-1))
                                {
                                    continue;
                                }
                                str = mes.substring(i,l).toCharArray();
                                Arrays.sort(str);
                                String sub = new String (str);
                                if(tmp[j].compareTo(sub)==0)
                                {
                                    prev[l+1] = j;
                                    cnt[l+1]++;
                                }
                            }
                        }
                        if(cnt[len+1]==0)
                        {
                            System.out.println("impossible");
                        }
                        else
                        {
                            if(cnt[len+1]>1)
                            {
                                System.out.println("ambiguous");
                            }
                            else
                            {
                                i = len+1;
                                int [] out = new int [10002];
                                int num = 0;
                                
                                while(i!=1)
                                {
                                     out[num++] = prev[i];
                                     i = i-length[prev[i]];
                                }
                                System.out.print(dic[out[num-1]]);
                                for(i = num-2; i >= 0; i--)
                                {
                                    System.out.print(" "+dic[out[i]]);
                                }
                                System.out.println();
                            }
                        }
		}
	}
}