1. 前文回顾
在字符串算法—字符串搜索中，我们实现了从一堆字符中搜索某个字符串的高效算法。
但如果要在一堆字符中找具有某些规律的字符串（要找的字符串是不确定的，但有规律），该如何设计算法？
本文将介绍NFA算法来解决此问题。
2. 正则表达式
首先，有规律的字符串是长什么样的呢？例如：ABBBBBBBBBA。
我们需要用一种方式来表达这个规律。于是我们就有了正则表达式。
ABBBBBBBBBA可以表达为AB*A。其中B*表示有N个B，N可以为0。
然后以下均是正则表达式：
[A-E]+表示：(A"B|C|D|E)(A|B|C|D|E)*
有了这些表达式后，我们就能让程序读懂字符串的规律，然后就是让它找出含有这规律的字符串在哪了。
3. NFA算法
本算法需要有向图基础，如果不了解有向图的，可以先看一下图表算法—有向图。
从例子中开始了解此算法：
现有正则表达式： ( ( A * B | A C ) D )。
我们通过某种构建方法（此方法稍后介绍），把这个正则表达式变成一个有向图：
我们将逐个逐个符号来读这个表达式。图中的0,1,2,3,...,10,11是阶段，当我们抵达第11阶段，则说明找到符合这表达式的字符串。
图中的线有两种颜色，红色的是过渡线，可以不读阶段里面的内容，直接跳到下一个指定阶段；蓝色是正常线，要先读阶段里面的内容，再改变阶段。
例如：第4阶段只能去第5阶段；第1阶段可以去第2阶段、第3阶段、第4阶段、第6阶段。
现在我们来看一下AAAABD是否符合这个表达式：
第一个字符为A，我们从第0阶段开始：
0,1阶段都是括弧，故符合。现在1可以去2、3、4和6，且2和6都是A，与第一个字符匹配，故两个阶段都去：
第二个字符为A，现在可以去2,4,7(其中去2的路线为2-3-2，去4的路线为2-3-4)，但匹配第二个字符的只有第2阶段，故去第2阶段：
第三个字符为A，现在可以去2,4(其中去2的路线为2-3-2，去4的路线为2-3-4)，但匹配第三个字符的只有第2阶段，故去第2阶段：
第四个字符为A，现在可以去2,4(其中去2的路线为2-3-2，去4的路线为2-3-4)，但匹配第四个字符的只有第2阶段，故去第2阶段：
第五个字符为B，现在可以去2,4(其中去2的路线为2-3-2，去4的路线为2-3-4)，但匹配第五个字符的只有第4阶段，故去第4阶段：
第六个字符为D，现在可以去9(其中去9的路线为4-5-8-9,由于5,8都是符号，不能与字符比较，故无视它们)，第9阶段匹配第五个字符，故去第9阶段：
没有第七个字符，且第9阶段可以直接抵达第11阶段，故这个字符串符合此表达式。
如果要从这个字符串中，找出有多少个符合此表达式的字符串，则经过上面的寻找，我们找到了第一个：AAAABD。
接下来寻找第二个，从第二个字符开始第0阶段，如果能顺利抵达第11阶段，说明AAABD也符合；否则，AAABD不符合。
然后第三个，从第三个字符开始第0阶段，如此类推，直到所有字符都开始过第0阶段为止，然后统计有多少个字符串符合，且记住它们的位置。
如此类推，我们可以找出整段字符中符合这个表达式的所有字符串，从而解决一开始提出的问题。
接下来就要看如何把这个正则表达式转化为有向图了：
首先，如果某阶段里含有的不是符号，而是字符，则可以直接去下一个阶段：
然后，如果遇到的是符号 * ,则分两种情况：
1. *所处的阶段的前一阶段是字符：
则加3条方向（不用担心重复加方向，因为代码中如果出现重复的，直接覆盖）。
2. *所处的阶段的前一阶段是右括弧：
也是加3条方向：与前一个左括弧加一个互相的方向，我们会用一个数字lp来记住前一个左括弧。
回到我们的这个例子，给*阶段添加方向：（符号用的线都是过渡线）
如果遇到的是左括弧或者是 " 则要把它们按顺序加到栈中，顺便给左括弧加一个指向下一个阶段的方向：（新建栈A）
如果遇到的是右括弧，则给它加一个指向下一个阶段的方向，且栈A输出数个元素，直到见到左括弧为止：
然后栈A输出一个元素（先进先出）：第5阶段的 " ，新建一个整数int or=5来记住它，并且给它加一个指向目前所处位置的右括弧处：
然后栈A输出一个元素：第1阶段的（，给它加一个指向or+1位置的方向：（如果有多个or，则分别指向各个or+1位置）
然后遇见的是第10阶段的），给它加一个指向下一个阶段的方向，且栈A输出数个元素，直到见到左括弧为止：
然后栈A输出一个元素：第0阶段的（，中途没见到 ", 因此不作操作：
然后去到第11阶段，构建完毕。
代码实现：
根据正则表达式构建有向图：
图中红色箭头处，它默认了栈下一个吐出来的是左括号，但如果吐出来的是 " ,则会出错，这里应该做一个针对连续吐出多个 | 的处理（加个判断）。
这段代码只处理了符号，应该添加代码给字符所处的阶段指向下一个阶段。
使用这个有向图来寻找字符串：
![[转]17种常用正则表达式](https://cdnss.haodaima.top/uploadfile/2024/0314/20240314060725585.gif)
