public class NFA
  { private static final int START = 0;
    private static final int ACCEPT = 1;
    private int NULL; // alphabet size
    private int N;
    private String alphabet;
    private Graph next[];
    private void NFAbuild(int from, int to, String re)                               { int plus =  re.indexOf('+'), len = re.length();
        if (len == 0) next[NULL].addEdge(from, to);
        else if (len == 1) 
          { char c = re.charAt(0);
            for (int i = 0; i < NULL; i++)
              if (c == alphabet.charAt(i) || c == '.') 
                next[i].addEdge(from, to); 
          }
        else if (plus > 0)
          {
            NFAbuild(from, to, re.substring(0, plus));
            NFAbuild(from, to, re.substring(plus+1));
          }
        else if (re.charAt(1) == '*')
          { 
            next[NULL].addEdge(from, N);
            NFAbuild(N, N, re.substring(0, 1));
            NFAbuild(N++, to, re.substring(2)); 
          }
        else
          {
            NFAbuild(from, N, re.substring(0, 1));
            NFAbuild(N++, to, re.substring(1));
          }
      }
    NFA(String ab, String re)                                     
      { 
        alphabet = ab;
        NULL = alphabet.length();
        next = new Graph[NULL+1];
        for (int i = 0; i <= NULL; i++)
          next[i] = new Graph(1+re.length());
        N = 2; 
        NFAbuild(0, 1, re);
for (int i = 0; i <= NULL; i++) System.out.print(next[i]);
      }
    public boolean simulate(Tape tape)
      { UniQueue nextQ, pcQ = new UniQueue(N);
        pcQ.put(next[NULL].reachable(START));
        while (!tape.isEmpty())
          { int ch = tape.read();
            nextQ = new UniQueue(N);
            while (!pcQ.isEmpty())
              nextQ.put(next[ch].adjQ(pcQ.get()));
            pcQ = new UniQueue(N); 
            while (!nextQ.isEmpty())
              pcQ.put(next[NULL].reachable(nextQ.get()));
System.out.println(ch + ":  { " + pcQ + "}");
          }            
        while (!pcQ.isEmpty())
          if (pcQ.get() == ACCEPT) return true;
        return false;
      }
    public static void main(String[] args)   
      { 
        NFA nfa = new NFA(args[0], args[1]);
        Tape tape = new Tape(args[2]);
        System.out.println(nfa.simulate(tape));
      }
  }