import java.util.HashSet;
import java.util.Set;
import java.util.Stack;
public class NFA {
private char[] re;
private Digraph G;
private int M;
public static void main(String...args) {
NFA nfa = new NFA(
"("
+ "(((("
+ "((((((((gold|metal)|lung)|larg intestine)|reduce)|fall)|crane)|aiki(do)*)|taiyin)"
+ "|((wood|wind)|liver))"
+ "|(water|kidney))"
+ "|(fire|fever))"
+ "|(earth))"
+ "(pair restriction not applied)*.*"
+ "(((("
+ "((((((((gold|metal)|lung)|larg intestine)|reduce)|fall)|crane)|aiki(do)*)|taiyin)"
+ "|((wood|wind)|liver))"
+ "|(water|kidney))"
+ "|(fire|fever))"
+ "|(earth))"
+ ")");
System.out.println(nfa.recognizes(""));
System.out.println(nfa.recognizes("gold"));
System.out.println(nfa.recognizes("gold hold water"));
System.out.println(nfa.recognizes("t-shirt damaged by fire"));
System.out.println(nfa.recognizes("gold damaged by fire"));
System.out.println(nfa.recognizes("lung damaged by whatever"));
System.out.println(nfa.recognizes("lung damaged by fever"));
System.out.println(nfa.recognizes("aikido connects to crane"));
}
public NFA(String regexp) {
Stack<Integer> ops = new Stack<>();
re = regexp.toCharArray();
M = regexp.length();
G = new Digraph(M + 1);
for(int i = 0; i < M; i++) {
int lp = i;
if(re[i] == '(' || re[i] == '|') ops.push(i);
else if(re[i] == ')') {
int or = ops.pop();
if(re[or] == '|') {
lp = ops.pop();
G.addEdge(lp, or + 1);
G.addEdge(or, i);
} else lp = or;
}
if(i < M - 1 && re[i + 1] == '*') {
G.addEdge(lp, i + 1);
G.addEdge(i + 1, lp);
}
if(re[i] == '(' || re[i] == '*' || re[i] == ')') G.addEdge(i, i + 1);
}
}
public boolean recognizes(String txt) {
Set<Integer> pc = new HashSet<>();
DirectedDFS dfs = new DirectedDFS(G, 0);
for(int v = 0; v < G.V(); v++) {
if(dfs.marked[v]) pc.add(v);
}
for(int i = 0; i < txt.length(); i++) {
Set<Integer> match = new HashSet<>();
for(int v : pc)
if(v < M)
if(re[v] == txt.charAt(i) || re[v] == '.')
match.add(v + 1);
pc = new HashSet<>();
dfs = new DirectedDFS(G, match);
for(int v = 0; v < G.V(); v++)
if(dfs.marked[v])
pc.add(v);
}
for(int v : pc)
if(v == M)
return true;
return false;
}
private class DirectedDFS {
boolean[] marked;
public DirectedDFS(Digraph G, int s) {
marked = new boolean[G.V()];
dfs(G, s);
}
public DirectedDFS(Digraph G, Set<Integer> source) {
marked = new boolean[G.V()];
for(Integer s : source) {
dfs(G, s);
}
}
private void dfs(Digraph G, int v) {
marked[v] = true;
for(int w : G.adj(v)) {
if(!marked[w]) {
marked[w] = true;
dfs(G, w);
}
}
}
}
private class Digraph{
private int V;
private int E;
private Set<Integer>[] adj;
public Digraph(int V) {
this.V = V;
adj = (Set<Integer>[])new HashSet[V];
for(int i = 0; i < V; i++) {
adj[i] = new HashSet<>();
}
}
public int V() {
return V;
}
public int E() {
return E;
}
public void addEdge(int from, int to) {
adj[from].add(to);
E++;
}
public Iterable<Integer> adj(int v) {
return adj[v];
}
}
}
