wordpress 招聘网站seo的中文含义是什么

字符串匹配之有限自动机

先来看什么是有限自动机?
首先，有限状态机是一个判定的机器，所谓判定的机器就是你给它输入一个模式，会的到一个$YES或者NO$的结果，比如要判断$1+1$的结果：

有限状态机就是构建出一个满足某个特定模式的判断系统
例如，对于$0101111001$串二进制数构建一个判断$1$的个数是否为偶数个的有限自动机

上图中，红色为自动机的出口，即$YES$的位置
如果一个串输入的最后停留在$YES$的位置，说明串中1的个数为偶数，如$0101$。
反之如果串输入后停在了其他的位置或者卡死在某一个位置，说明这个串是$NO$的，如$0100$。

字符串匹配自动机
对于字符串的处理，我们可以利用有限自动机来判断，对模式串$P$构建一个有限自动机，用其来判断文本串$T$，如果文本串$T$可以到达$YES$的位置，说明文本串$T$中包含了模式串$P$
例如，对$P = "ababaca"$构建有限自动机

上面的有限自动机中，$0$为开始，输入模式串P后分别经过了{$0，1，2，3，4，5，6，7$}到达了$7$的位置，为$YES$，我们用一个表格来表示文本串$T$在自动机里面的路径

对于任意的字符串状态机，我们都能构建出上面的表格(后面在代码中称为跳转表)，利用上面的状态机，逐次读入$T$的字符，如果状态机跳转到状态$7$，说明文本$T$包含字符串$P$。
如输入文本串$T = "abababacaba"$，

上表中模式串$P$和文本串$T$匹配成功的地方被标上了黄色阴影，红色的$7$表示$YES$状态，即$T = "abababacaba"$中包含$P = "ababaca"$。

为了方便代码表述，把文本串$T$中的字符每输入一个到状态机，即$T[i]$在状态机每走一步，称为一次变迁，用$q$表示状态，$g$表示变迁函数，$q = g(q，T[i])$
为了方便在程序中构建出跳转表，这里引入后缀的概念，给定两个字符串$A[0..n]$和$B[0..m]$如果$B[0..m]$等于$A[x..m]$，则$A$是$B$的后缀。对于上述字符串模式$P = "ababaca"$，文本串$T = "abababacaba"$，一次读入$T$的一个字符，用$S$表示当前读入的T的字符，当读取第一个字符$S=a$时，$P[1]$是$S$的后缀，把$S$的长度记为$k$，这样反复操作：

S=a，k = 1， P[1] 是S的后缀
S=ab， k = 2， P[1，2] 是S的后缀
S=aba， k = 3， P[1，2，3]是S的后缀
S=abab， k= 4， P[1，2，3，4]是S的后缀
S=ababa， k = 5， P[1，2，3，4，5]是S的后缀
S=ababab， k = 4， P[1，2，3，4]是S的后缀
S=abababa， k = 5， P[1，2，3，4，5]是S的后缀
S=abababac， k = 6， P[1，2，3，4，5，6]是S的后缀
S=abababaca， k = 7， P[1，2，3，4，5，6，7]是S的后缀
S=abababacab， k =2， P[1，2] 是S的后缀
S=abababacaba， k = 3， P[1，2，3] 是S的后缀。

从上面可以看出，$k$的值就是跳转表中阴影的部分，因此可以通过模拟为这样的操作来构建跳转表：
(可以参照上面的跳转表来看这段话)
假定组成$P$和$T$的字符集$∑$={$a，b，c$}，$P$含有$m$个字母，于是我们要构建的自动机含有$m$个状态节点。假设我们当前处于状态节点$q$，那么当下一个字符是$a$和$b$时，我们要怎样跳转呢?如果用$P_q$表示长度为$q$的$P$的前缀，以$q=4，P="ababaca"$，$P_q = "abab"$为例，当输入为$a$时，构建字符串$S=P_q+'a' = "ababa"$，此时字符串$P$从第一个字符开始，连续$5$个字符可以作为$S$的后缀，所以当状态机处于状态$4$，输入为$a$时，跳转的下一个状态为$5$；同理，输入为$b$时，$S = P_q+'b' = "ababb"$，此时从$P$开始，连续$0$个字符为$S$的后缀.于是状态机处于状态$4$是，如果读入字符为$b$，那么跳转的下一个状态为$0$，读入$c$也同理。重复这些步骤，便能构建出上面的跳转表。
代码实现：

typedef vector<map<char, int> > TAB;//判断P[0..k-1]是否为P[0...q-1]+ch的后缀
bool IsPrefix(const char*P, int k, int q, char ch)
{if (0 == k)return true;if (1 == k)return (P[0] == ch);return (P[k - 1] == ch && (strncmp(P, P + q - k + 1, k - 1) == 0));
}//构建跳转表
TAB TransitionFun(const char* P,const char* CharTab)
{int m = strlen(P);TAB TransitionMap(m+1);for (int q = 0; q < m; ++q)//q表示状态{int j = 0;while (CharTab[j] != '\0'){int k = min(m + 1, q + 2);while (!IsPrefix(P, k, q, CharTab[j]))--k;TransitionMap[q][CharTab[j]] = k;++j;}}return TransitionMap;
}void AutoMatcherSearch(const char* T, const char* P,const char* CharTab)//Chartab表示字母表集
{int n = strlen(T);int m = strlen(P);int q = 0;//q表示状态TAB g = TransitionFun(P,CharTab);for (int i = 0; i < n; ++i){q = g[q][T[i]];//变迁if (q == m)//达到YES状态,输出偏移量printf("%d\n", i - m+1);}
}

代码中第$14$行的函数为构建跳转表的函数；$23$~$26$行为确定一个数$k$，使得$k$满足$P[0..k-1]$为$P[0..q-1]+ch$的后缀，该判断有两层循环，复杂度为$O(m^2)$；构建跳转表的函数有两层循环，循环次数为$O(m*|∑|)$，所以构建跳转表的总复杂度为：$O(m^3|∑|)$,匹配时需要$O(n)$的时间。

参考：
1.《算法导论》
2.https://blog.csdn.net/tyler_download/article/details/52549315