3093854_ac_1218ms_22160k.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
                {
                    i = len+1;
                    int [] out = new int [10002];
                    int num = 0;
                    
                    while(i!=1)
                    {
                        if(cnt[i]!=1)
                        {
                            System.out.println("ambiguous");
                            break;
                        }
                        out[num++] = prev[i];
                        i = i-length[prev[i]];
                    }
                    if(i!=1)
                    {
                        continue;
                    }
                    System.out.print(dic[out[num-1]]);
                    for(i = num-2; i >= 0; i--)
                    {
                        System.out.print(" "+dic[out[i]]);
                    }
                    System.out.println();
                }
            }
	}
}