Reduce a string using grammar-like rules

Question

I've got a program in Java which simplifies input string using grammar-like rules. Length of string is up to 200 and number of rules is up to 300. In big cases it works too slow, so I need some advice on time optimization of the code.

Example input: 4 4; a b a b; a b -> b; a b -> c; b a -> a; c c -> b

Program show all the simple chars that can be received from the input string a b a b using the rules. For this example it is b c. For string of length 155 and number of rules 92 the algorithm should work 0.05 seconds faster.

import java.util.Map;
import java.util.HashMap;
import java.util.Set;
import java.util.HashSet;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main {
 static int n, p;
 static String input;
 String[] textStr;
 static BufferedReader buff;
 static Map<String, Set<String>> cache = new HashMap();
 static Map<String, ArrayList<Character>> rules = new HashMap();
 public static void main(String[] args) {
 buff = new BufferedReader(new InputStreamReader(System.in));
 try{
 String tem = buff.readLine();
 String textStr[] = tem.split("\\s+");
 n = Integer.parseInt(textStr[0]);
 p = Integer.parseInt(textStr[1]);
 tem = buff.readLine();
 input = tem.replaceAll("\\s+","");
 for(int i = 0; i < p; i++){
 tem = buff.readLine();
 textStr = tem.split("\\s+");
 Character cl = textStr[0].charAt(0);
 Character fa = textStr[1].charAt(0);
 Character re = textStr[2].charAt(0);
 if(!rules.containsKey(cl+" "+fa)){
 rules.put(cl + " " + fa, new ArrayList());
 }
 rules.get(cl+" "+fa).add(re);
 }
 Set<String> temp = simplify(input);
 List<String> te = new ArrayList<>(temp);
 Collections.sort(te);
 for(int i = 0; i < temp.size(); i++){
 System.out.print(te.get(i)+" ");
 }
 }catch(IOException e){
 System.out.println("Error");
 }
 finally {
 try {
 buff.close();
 } catch (IOException e) {
 System.err.println("Error");
 }
 }
 }
 public static Set<String> simplify(final String in) {
 if(cache.containsKey(in)){
 return(cache.get(in));
 }
 Set<String> ret = new HashSet<>();
 if (in.length() == 1) {
 ret.add(in);
 return ret;
 }
 for (int i = 1; i < in.length(); i++) {
 String head = in.substring(0, i);
 String tail = in.substring(i);
 for (String c2 : simplify(tail)) {
 for (String c1 : simplify(head)) {
 ArrayList<Character> rep = rules.get(c1+" "+ c2);
 if (rep != null) {
 for (Character c : rep) {
 ret.add(c.toString());
 }
 }
 }
 }
 }
 cache.put(in, ret);
 return ret;
 }
}

• Chantz: Can you clarify the question further by explaining the example rules?
• user2875945: @Chantz for example rule "a b b" means that if there is a pair "ab" in the input string this pair can be replaced with "b"
• Chantz: Oh. Ok. So you have 2 rules which have same input a b but different output b & c. What decides which reduction rule to pick when?
• Pimgd: Why is the output not b for the example? If a b can be converted to c and c c can be converted to b, why is a b a b not c c and then b?

Answer 1

n is unused.

You write to it here:

 n = Integer.parseInt(textStr[0]);

But you don't do anything with it.