3107597_wa.java

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

import java.util.*;
import java.io.*;

public class Main
{

	static final int inf = 2100000000;
	
	public static void main(String [] args)	throws IOException
	{
		new Main().solve();
	}

	private void solve()	throws IOException
	{
            BufferedReader br = new BufferedReader (new InputStreamReader(System.in));
            int i, j, n;
            String mes;
            String [] dic = new String [100002];
            int [] pos = new int [260];
            int [] end = new int [260];
            int [] length = new int [100002];

            n = 0;
            while(true)
            {
            	dic[n] = br.readLine();
            	if(dic[n].compareTo("")==0)
            	{
            		break;
            	}
            	if(usable(dic[n]))
            	{
            		n++;
            	}
            }
            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();
            	end[dic[i].charAt(0)] = i;
            }
            while(true)
            {
            	int k, K, min;
            	mes = br.readLine();
            	int len = mes.length();
            	int [] out = new int [260];
            	if(mes.compareTo("0")==0)
            	{
            		break;
            	}
            	min = inf;
            	K = 1;
            	for(k = 0; k < 26; k++)
            	{
            		int [] cnt = new int [260];
            		int [] prev = new int [260];
            		
            		Arrays.fill(cnt, -1);
            		cnt[1] = 0;
            		for(i = 0; i < len; i++)
            		{
            			if(cnt[i+1]==-1)
            			{
            				continue;
            			}
            			for(j = pos[mes.charAt(i)]; j <= end[mes.charAt(i)]; j++)
            			{
            				int l = i + length[j];
            				if(l > len)
            				{
            					break;
            				}
            				if(dic[j].compareTo(mes.substring(i,l))==0)
            				{
            					if(cnt[l+1]==-1||cnt[l+1]>cnt[i+1]+1)
            					{
            						prev[l+1] = j;
            						cnt[l+1] = cnt[i+1]+1;
            					}
            				}
            			}
            		}
            		mes = change(mes);
            		if(cnt[len+1]!=-1&&cnt[len+1]<min)
            		{
            			i = len+1;
            			boolean error;
            			int last, now;
            			
            			last = 0;
            			error = false;
            			while(i!=1)
            			{
            				now = length[prev[i]];
            				if(now==1&&last==1)
            				{
            					error = true;
            					break;
            				}
            				last = now;
            				i = i-length[prev[i]];
            			}
            			if(!error&&len>2*cnt[len+1])
            			{
            				K = k;
            				min = cnt[len+1];
            				out = copyfrom(prev, prev.length);
            			}
            		}
                }
            	if(min==inf)
            		System.out.println("NO SOLUTIONS");
            	else
            	{
            		System.out.print("k="+K+":");
            		i = len+1;
            		int prev[] = new int [260];
            		prev = copyfrom(out, out.length);
            		int num = 0;
            		while(i!=1)
                    {
                        out[num++] = prev[i];
                        i = i-length[prev[i]];
                    }
            		for(i = num-1; i >= 0; i--)
            		{
            			System.out.print(" "+dic[out[i]]);
            		}
            		System.out.println();
            	}
            }
	}

	private int[] copyfrom(int[] prev, int length) 
	{
		int ret [] = new int [length];
		
		for(int i = 0; i < length; i++)
		{
			ret[i] = prev[i];
		}
		return ret;
	}

	private String change(String mes) 
	{
		String ret;
		int i;
		char ch;
		
		ret = "";
		for(i = 0; i < mes.length(); i++)
		{
			if(mes.charAt(i)=='a')
				ch = 'z';
			else
				ch = (char)(mes.charAt(i)-1);
			ret += ch;
		}
		return ret;
	}

	private boolean usable(String str) 
	{
		int i;
		
		for(i = 0; i < str.length(); i++)
		{
			if(str.charAt(i)<'a'||str.charAt(i)>'z')
			{
				return false;
			}
		}
		return true;
	}
}