不知道各位读者在了解正则表达式的时候有没有产生过这样一个问题：为什么我们必须用正则表达式？有没有代替正则表达式的东西？正则表达式的核心原理是什么？
要解答这个问题，就必须要了解有限自动机，这是正则表达式的核心。
有限自动机实际上是一个识别器（recognizer），它提供一个状态转移表，即在当前状态下，接受一个新的输入后，系统应该转移到什么状态。用语言描述显得有些晦涩，下面我们来看一个具体的例子。
假定要查找的字符串为P=”ababaca”, 被查找的文本为T=”abababacaba”。一次读入T的一个字符，用S表示当前读入的T的字符。那我们需要做的就是，寻找最长的P的前缀，使其可以构成S的后缀，我们把匹配上的P的前缀长度记作k。于是就能得到下面这个序列。
P = ”ababaca”
T = ”abababacaba”
- S= a color{red}{a} a, k = 1, P[1] a color{red}{a} ababaca
- S= a b color{red}{ab} ab, k = 2, P[1,2] a b color{red}{ab} ababaca
- S= a b a color{red}{aba} aba, k = 3, P[1,2,3] a b a color{red}{aba} ababaca
- S= a b a b color{red}{abab} abab, k= 4, P[1,2,3,4] a b a b color{red}{abab} ababaca
- S= a b a b a color{red}{ababa} ababa, k = 5, P[1,2,3,4,5] a b a b a color{red}{ababa} ababaca
- S=ab a b a b color{red}{abab} abab, k = 4, P[1,2,3,4] a b a b color{red}{abab} ababaca
- S=ab a b a b a color{red}{ababa} ababa, k = 5, P[1,2,3,4,5] a b a b a color{red}{ababa} ababaca
- S=ab a b a b a c color{red}{ababac} ababac, k = 6, P[1,2,3,4,5,6] a b a b a c color{red}{ababac} ababaca
- S=ab a b a b a c a color{red}{ababaca} ababaca, k = 7, P[1,2,3,4,5,6,7] a b a b a c a color{red}{ababaca} ababaca
- S=abababac a b color{red}{ab} ab, k =2, P[1,2] a b color{red}{ab} ababaca
- S=abababac a b a color{red}{aba} aba, k = 3, P[1,2,3] a b a color{red}{aba} ababaca
显而易见的，当k与P.size()相同时，就可以认为我们在T中找到了P，而k与P.size()相同的次数，就是在T中匹配到P的次数。
这个例子，运行了T.size()次，但每次都需要从S中寻找P。如果能够构造一个方法，使得只需一次运行便能知道从P开始，连续读取几个字符构成的字符串是S的后缀。这个方法，就需要上面我们提到的有限状态自动机。
思考一个问题，为什么要使用S的后缀和P进行匹配？
后缀非常重要，使用后缀进行匹配，就不需要关心前面的内容，因为前面的内容一定已经在之前匹配过了。在这种情况下，只需要关心在当前后缀上加入一个新字符，匹配状态会如何变化。
把P能够在S中匹配到的长度看做一种状态，那么总状态的数量就是P的长度，按照P匹配到的长度数为状态命名，就能得到一个状态转移表。
| 输入 | a | b | c |
|---|---|---|---|
| 状态0 | 1 color{red}{1} 1 | 0 | 0 |
| 状态1 | 1 | 2 color{red}{2} 2 | 0 |
| 状态2 | 3 color{red}{3} 3 | 0 | 0 |
| 状态3 | 1 | 4 color{red}{4} 4 | 0 |
| 状态4 | 5 color{red}{5} 5 | 0 | 0 |
| 状态5 | 1 | 4 | 6 color{red}{6} 6 |
| 状态6 | 7 color{red}{7} 7 | 0 | 0 |
| 状态7 | 1 | 2 | 0 |
正则表达式就是先将正则表达式字符串转换成有限自动机，然后进行匹配的。
深入有限自动机 DFA和NFA有限自动机又分为确定有限自动机（DFA）和非确定有限自动机（NFA），DFA不包含空集，且对于每一个状态的相同输入，只会产生一个状态转移。NFA则会包含指向自身的状态，以及对相同输入的不同输出。NFA可以转换为DFA，但消耗更多的空间。
正则表达式先被翻译成NFA，然后视情况转换为DFA。
kmp作为优秀的单字符串匹配算法，其实现思路其实就是有限自动机。但kmp的区别是，需要匹配的子串是固定的，而在正则表达式中，需要匹配的是正则表达式规则。
class StringAutomaton {
private HashMap> jumpTable = new HashMap>();
String objectString = "";
private final int alphaSize = 3;
public StringAutomaton(String p) {
this.objectString = p;
makeJumpTable();
}
private void makeJumpTable() {
int m = objectString.length();
// q为当前状态
for (int q = 0; q <= objectString.length(); q++) {
// 遍历在当前状态可达的所有状态
for (int k = 0; k < alphaSize; k++) {
char c = (char)('a' + k);
String Pq = objectString.substring(0, q) + c;
int nextState = findSuffix(Pq);
System.out.println("from state " + q + " receive input char " + c + " jump to state " + nextState);
// 获取当前状态对应的跳转表
HashMap map = jumpTable.get(q);
if (map == null) {
map = new HashMap();
}
// 保存当前状态下，输入c时，跳转到什么状态
map.put(c, nextState);
jumpTable.put(q, map);
}
}
}
private int findSuffix(String Pq) {
int suffixLen = 0;
int k = 0;
while(k < Pq.length() && k < objectString.length()) {
int i = 0;
for (i = 0; i <= k; i++) {
if (objectString.charAt(i) != Pq.charAt(Pq.length() - 1 - k + i)) {
break;
}
}
if (i - 1 == k) {
suffixLen = k+1;
}
k++;
}
return suffixLen;
}
public int match(String T) {
Integer q = 0;
System.out.println("Begin matching...");
for (int n = 0; n <= T.length(); n++) {
HashMap map = jumpTable.get(q);
int oldState = q;
q = map.get(T.charAt(n));
if (q == null) {
return -1;
}
System.out.println("In state " + oldState + " receive input " + T.charAt(n) + " jump to state " + q);
if (q == objectString.length()) {
return q;
}
}
return -1;
}
}
参考资料：
https://blog.csdn.net/tyler_download/article/details/52549315
https://www.sardinefish.com/blog/336
