总的来说，分为两种边 匹配边 和 episo边 。
状态转移是， 从 一个状态集合， 转移到 另一个 状态集合。
一个状态集合中的 存在 匹配边的所有 状态， 可以通向另状态集合， 该集合可以通过 episo边进行扩展，到此实现了状态的转移。
例如下边的例子 起始状态集合为{0，1，2，3，4，6} 12346是通过episo扩展得到的。
该集合中的 {2,4,6}存在匹配边， 若当前输入为A, 则{2,6}可以实现匹配，{2，6}转移到{3，7} ，而{3，7}再扩展（通过episo边）得到{2，3，4，7}.
由此 实现了 {0，1，2，3，4，6} 状态集 到 {2，3，4，7}状态集的转换。
正则表达式的匹配算法是基于NFA的，它的运行模式是这样的，有两种装换状态，黑色的和红色的，如下图。黑色的表示需要字符才能装换，如2状态，就需要接受一个字符A才能装到3,；红色状态代表可以自动进行装换。如3状态，可以自动转化到状态2和状态4。NFA运行的过程为，每一个状态都需要自动装换，直到不能进行自动装换。然后和进行黑色的装换，注意，每个可达的状态都需要进行处理。如从0状态开始，可以通过红色转换到达的状态为1，2，3，4，6，加上0，一共是6个状态。如果要匹配的第一个字符是A，2状态可以转化为3，然后3进行自动转换，到达2，和4，6状态接受A到达状态7，不能进行自动转化。所以第二次等待的状态为2，3，4，7。
NFA corresponding to the pattern ( ( A * B | A C ) D )
如何记录这个NFA，黑色的部分可以使用正则表达式本身来保存，而红色的部分可以使用有向图来表示。那么如何构造这个NFA，在《算法（第四版）》中给出了下面的图：
NFA construction rules
有了这个图，大致可以得到代码，这里有一个技巧，就是使用栈进行括号的匹配。遇到左括号就压栈，遇到有括号就检查栈中有没有左括号，如果没有匹配就失败了。如果匹配到最后，栈中还有左括号，也失败了。这里NFA的构造也用了上面这个技巧，只不过多加了一个字符。
模拟NFA的运行也是比较容易的，就是先进行自动转化，初始化。然后对于每一个字符，先进行黑色转换，然后进行红色装换，重复上面过程，直到最后一个字符，如果在最后的状态中有结束状态，则认为匹配成功，否则匹配失败。具体的代码如下：
#include<iostream> #include<vector> #include<string> #include<queue> #include<stack> using namespace std; void nfa(vector<vector<int> > &graph, string &txt){ stack<int> ops; int n = txt.size(); for(int i=0;i<n;i++){ int lp = i; if(txt[i] == '(' || txt[i] == '|'){ ops.push(i); }else if(txt[i] == ')'){ int op = ops.top(); ops.pop(); if(txt[op] == '|'){ lp = ops.top(); ops.pop(); graph[op].push_back(i); graph[lp].push_back(op+1); }else{ lp = op; /* find closest '(' */ } } if(i<n-1 && txt[i+1] == '*'){ graph[lp].push_back(i+1); graph[i+1].push_back(lp); } if(txt[i] == '(' || txt[i] == '*' || txt[i] == ')'){ graph[i].push_back(i+1); } } } void bfs(vector<vector<int> > &graph, vector<int> &vertex){ int n = graph.size(); vector<bool> marked(n+1,false); queue<int> q; for(int i=0;i<vertex.size();i++){ marked[vertex[i]] = true; q.push(vertex[i]); } while(q.size() > 0){ int v = q.front(); q.pop(); for(int i=0;i<graph[v].size();i++){ if( marked[ graph[v][i] ] == false){ vertex.push_back( graph[v][i] ); marked[ graph[v][i] ] = true; q.push( graph[v][i] ); } } } } bool match(string txt,string pattern){ vector<vector<int> > graph; for(int i=0;i<=pattern.size();i++){ graph.push_back(vector<int>()); } nfa(graph,pattern); vector<int> vertex; vertex.push_back(0); bfs(graph,vertex); for(int i=0;i<txt.size();i++){ vector<int> v; for(int j=0;j<vertex.size();j++){ if(vertex[j] < pattern.size() && ( txt[i] == pattern[vertex[j]] || pattern[vertex[j]] == '.') ){ v.push_back(vertex[j] + 1); } } bfs(graph,v); vertex = v; } for(int i=0;i<vertex.size();i++){ // 若状态集 中 存在最后一个AC(接收)状态，即为匹配成功。 if(vertex[i] == pattern.size()){ return true; } } return false; } int main(){ string s; bool ret; while(cin>>s){ ret = match(s,"((A*B|AC)D)"); if(ret == true){ cout<<s<<endl; }else{ cout<<"fail"<<endl; } } return 0; }重点是NFA的构造。
Q10 : 给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
class Solution { ArrayList<ArrayList<Integer>> G; // 红边 构成的 邻接表 图 public boolean isMatch(String s, String p) { int lenp = p.length(); G = new ArrayList<>(); // 总状态数 比 p.length 多一个， 最后一个状态时 接收状态。到达接收状态就是成功了。 for(int i = 0; i <= lenp; i++){ G.add(new ArrayList<>()); } nfa(p); ArrayList<Integer> fromSet = new ArrayList<>(); fromSet.add(0); // 扩展初试 状态集 bfs(fromSet); int n = s.length(); for(int i = 0; i < n; i++){ ArrayList<Integer> toSet = new ArrayList<>(); for(int j = 0; j < fromSet.size(); j++){ //System.out.println(fromSet.get(j)+"+++"+fromSet.size()); if(fromSet.get(j) < p.length() && (p.charAt(fromSet.get(j)) == s.charAt(i) ||p.charAt(fromSet.get(j)) == '.' )){ toSet.add(fromSet.get(j)+1); } } bfs(toSet); fromSet = toSet; } for(int i = 0; i < fromSet.size(); i++){ if(fromSet.get(i) == p.length()){ return true; } } return false; } public void nfa(String pat){ int n = pat.length(); for(int i = 0; i < n; i++){ if(i < n-1 && pat.charAt(i+1) == '*'){ G.get(i+1).add(i); G.get(i).add(i+1); } if(pat.charAt(i) == '*'){ G.get(i).add(i+1); // i+1 可能越界，所以取出的时候要注意判别。 } } } // 把一个集合 进行 episo扩展(保留原有元素，并扩展) public void bfs(ArrayList<Integer> set){ int n = G.size(); boolean[] vis = new boolean[n+1];// 标记该点是否访问 LinkedList<Integer> queue = new LinkedList<>(); // 一次性入栈 for(Integer it : set){ queue.add(it); vis[it] = true; } while(!queue.isEmpty()){ int v = queue.getFirst(); queue.removeFirst(); for(int i = 0; i < G.get(v).size(); i++){ if(!vis[G.get(v).get(i)]){ set.add(G.get(v).get(i)); vis[G.get(v).get(i)] = true; queue.addLast(G.get(v).get(i)); } } } } }
