srm 234 div2 1000pts

这题仔细分析一下还是蛮简单的，利用正则表达式来做。正则表达式分为四种：a+，b+，a+b+,其它（这种正则表达式比较复杂）但没必要去判断它，直接贴代码了：

public class DerivationDisplay {
   public String[] getDerivation(String input) {
		String[] ans=null;
		String p1="a+";
		String p2="b+";
		String p3="a+b+";//a+(a+|b+)b+
		
		LinkedList<String> ll=new LinkedList<String>();
		
		if(input.matches(p1)){
			doP1(ll,input);
		}else if(input.matches(p2)){
			doP2(ll,input);
		}else if(input.matches(p3)){
			doP3(ll,input);
		}else{
			doP4(ll,input);
		}
		ans=ll.toArray(new String[0]);
		return ans;
   }
   
   void doP1(LinkedList<String> ll,String input){
   		ll.add("S");
   		ll.add("T");
   		ll.add("A");
   		char c=input.charAt(0);
   		StringBuffer sb=new StringBuffer();
   		for(int i=0;i<input.length();i++){
   			sb.append(c);
   			ll.add(sb.toString()+(i==input.length()-1?"":"A"));
   		}
   }
   
   void doP2(LinkedList<String> ll,String input){
   		ll.add("S");
   		ll.add("T");
   		ll.add("B");
   		char c=input.charAt(0);
   		StringBuffer sb=new StringBuffer();
   		for(int i=0;i<input.length();i++){
   			sb.append(c);
   			ll.add(sb.toString()+(i==input.length()-1?"":"B"));
   		}
   }
   
   void doP3(LinkedList<String> ll,String input){
  		ll.add("S");
  		ll.add("T");
  		StringBuffer pre=new StringBuffer();
  		StringBuffer suf=new StringBuffer();
  		while(input!=null&&(!input.equals(""))&&input.charAt(0)=='a'&&input.charAt(input.length()-1)=='b'){
  			pre.append('a');
  			suf.append('b');
  			ll.add(pre.toString()+"T"+suf.toString());
				input=input.substring(1,input.length()-1);
  		}
  		
  		if(input.matches("a+")){
  			ll.add(pre.toString()+"A"+suf.toString());
  			for(int i=0;i<input.length();i++){
  				pre.append('a');
  				ll.add(pre.toString()+(i==input.length()-1?"":"A")+suf.toString());
  			}
  		}else if(input.matches("b+")){
  			ll.add(pre.toString()+"B"+suf.toString());
  			for(int i=0;i<input.length();i++){
  				pre.append('b');
  				ll.add(pre.toString()+(i==input.length()-1?"":"B")+suf.toString());
  			}
  		}//else
  	}
   void doP4(LinkedList<String> ll,String input){
  		ll.add("S");
  		ll.add("bUa");
  		input=input.substring(1,input.length()-1);
  		StringBuffer pre=new StringBuffer();
  		pre.append('b');
  		StringBuffer suf=new StringBuffer();
  		suf.append('a');
  		while(input!=null&&!input.equals("")){
  			if(input.charAt(0)=='a'){
  				pre.append('a');
  			}else{
  				pre.append('b');
  			}
  			input=input.substring(1,input.length());
				String con="";
				if(input!=null&&!input.equals("")){
					con="U";
				}
				ll.add(pre.toString()+con+suf.toString());
  		}//while
  	}
}