大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
阅读博客的朋友可以参看视频:
如何进入google,算法面试技能全面提升指南
什么叫有限状态自动机
先看一个图:
上面这个图描述的就叫一个有限状态自动机,图中两个圆圈,也叫节点,用于表示状态,从图中可以看成,它有两个状态,分别叫0和1. 从每个节点出发,都会有若干条边,当处于某个状态时,如果输入的字符跟该节点出发的某条边的内容一样,那么就会引起状态的转换。例如,如果当前状态处于0,输入是字符a,那么状态机就会从状态0进入状态1.如果当前状态是1,输入字符是b或a,那么,状态机就会从状态1进入状态0.如果当前所处的状态,没有出去的边可以应对输入的字符,那么状态机便会进入到错误状态。例如,如果当前处于状态0,输入字符是c,那么状态机就会出错,因为从状态0开始,没有哪条边对应的字符是c.
状态机会有一个初始节点,和一个接收节点,以上图为例,我们可以设置初始节点为0,接收节点为1,当进行一系列的输入,使得状态机的状态不断变化,只要最后一个输入使得状态机处于接收节点,那么就表明当前输入可以被状态机接收。例如对应字符串”abaaa”, 从初始节点0开始,状态机根据该字符串的输入所形成的状态变化序列为:{0,1,0,1,0,1}。由于最后状态机处于状态1,所以该字符串可以被状态机接收。如果输入的字符串是:abbaa, 那么状态机的变化序列为:{0,1,0,0,1,0}, 由于最后状态机处于非接收状态,因此这个字符串被状态机拒绝。
在程序中,我们一般使用二维表来表示一个状态机,例如上面的状态机用二维表来表示如下:
输入 | a | b |
---|---|---|
状态0 | 1 | 0 |
状态1 | 0 | 0 |
通过查表,我们便可知道状态机的转换,例如处于状态0,输入字符是a时,我们从表中得到的数值是1,也就是说处于状态0,输入是字符a,那么状态机将转入状态节点1.
一个文本匹配流程的描述
接下来我们看看一个文本的匹配流程,假定要查找的字符串为P=”ababaca”, 被查找的文本为T=”abababacaba”. 一次读入T的一个字符,用S表示当前读入的T的字符,一开始读入一个字符,于是S=a.然后看看,从P开始,连续几个字符所构成的字符串可以成为S的后缀,由于当前S只有一个字符a,于是从P开始,连续1个字符所形成的字符串”a”,可以作为S的后缀。把这个字符串的长度记为k,于是此时k 等于1. 继续从T中读入字符,于是S=”ab”, 此时,从P开始,连续两个字符所构成的字符串”ab”可以作为S的后缀,于是k = 2.反复这么操作,于是便有以下序列:
- 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的后缀。
注意看第9步,P的长度是7,整个字符串P成为了字符串S的后缀,而此时的S是文本T的前缀,这不就表明文本T含有字符串P了吗。在每一个步骤中,我们都需要从P的第一个字符开始,看看最多能连续读取几个字符,使得他们能成为S的后缀,假设P的字符个数为m, 那么这个读取过程最多需要读取m个字符,于是复杂度为O(m). 如果有某种办法,使得我们一次就可以知道从P开始,连续读取几个字符就可以构成S 的后缀,假设文本T含有n个字符,那么我们就可以在O(n)的时间内判断,T是否含有字符串P.因为上面的步骤最多可以执行n次。
于是当前问题变成,构造一个方法,使得一次运行便能知道从P开始,连续读取几个字符能使,得这几个字符构成的字符串是S的后缀。这个方法,就需要上面我们提到的有限状态自动机。
用于字符串匹配的自动机
假定字符串P和文本T只由a,b两个字符组成,也就是字符集为 ∑ ={a,b,c}, P含有m个字母,于是,我们要构造的自动机就含有m个状态节点。假设我们当前处于状态节点q, 那么当下一个输入字符是a和b时,从当前节点q该跳转到哪一个节点呢? 如果用 Pq 来表示长度为q的P的前缀,以q=4, p=”ababaca”, Pq =”abab”, 那么当处于状态4, 当输入为a时,我们构造字符串 S = Pq + ‘a’ = “ababa”, 然后看看字符串P从第一个字符开始,连续几个字符所构成的字符串可以成为S的后缀,就当前S为例,从第一个字符开始,连续5个字符,也就是P[1,2,3,4,5]可以作为S的后缀,于是,我们就有,当状态机处于节点4,输入为a时,跳转的下个状态就是5. 同理,当处于状态q=4,输入为字符b时,S = Pq + ‘b’ = “ababb”,此时从P开始,连续读取0个字符才能形成S的后缀,于是当状态机处于状态4,如果读入字符是b, 那么跳转的下一个状态是0,同理,如果输入字符是c, 那么S = Pq + ‘c’ = “ababc”, 此时从P开始,连续读取0个字符所形成的空字符串才能作为S的后缀,于是当状态机处于状态节点4,输入字符为c时,跳转到节点0. 如果q从0开始,一直到m,反复运用刚才提到的步骤,便会产生下面这个跳转表:
输入 | a | b | c |
---|---|---|---|
状态0 | 1 | 0 | 0 |
状态1 | 1 | 2 | 0 |
状态2 | 3 | 0 | 0 |
状态3 | 1 | 4 | 0 |
状态4 | 5 | 0 | 0 |
状态5 | 1 | 4 | 6 |
状态6 | 7 | 0 | 0 |
状态7 | 1 | 2 | 0 |
利用上面的状态机,依次读入T的字符,如果状态机跳转到状态q,那就表明从P的第一个字符开始,连续读取q个字符,所形成的字符串可以构成是S的后缀,也就是说,当我们的状态机跳转到状态7时,我们就可以得知文本T,包含字符串P.
我们走一遍这个过程,首先状态机处于状态0,读入T[0]=a, S= a, 查表可知进入状态1,读入T[1]=b, S=ab, 查表可知,进入状态2,读入T[2]=a,查表可知进入状态3,读入T[3]=b, S=abab,查表可知进入状态4,读入T[4]=a,S=ababa,查表可知进入状态5,读入T[5]=b,S=ababab,查表可知进入状态4,读入T[6]=a, S=abababa,查表可知进入状态5,读入T[7]=c,S=abababac,查表可知进入状态6,读入T[8]=a,S=abababaca,查表可知进入状态7,此时,我们可以得出结论,文本T包含有字符串P.
代码实现
import java.util.HashMap;
public class StringAutomaton {
private HashMap<Integer, HashMap<Character, Integer>> jumpTable = new HashMap<Integer, HashMap<Character, Integer>>();
String P = "";
private final int alphaSize = 3;
public StringAutomaton(String p) {
this.P = p;
makeJumpTable();
}
private void makeJumpTable() {
int m = P.length();
for (int q = 0; q <= m; q++) {
for (int k = 0; k < alphaSize; k++) {
char c = (char)('a' + k);
String Pq = P.substring(0, q) + c;
int nextState = findSuffix(Pq);
System.out.println("from state " + q + " receive input char " + c + " jump to state " + nextState);
HashMap<Character, Integer> map = jumpTable.get(q);
if (map == null) {
map = new HashMap<Character, Integer>();
}
map.put(c, nextState);
jumpTable.put(q, map);
}
}
}
private int findSuffix(String Pq) {
int suffixLen = 0;
int k = 0;
while(k < Pq.length() && k < P.length()) {
int i = 0;
for (i = 0; i <= k; i++) {
if (Pq.charAt(Pq.length() - 1 - k + i) != P.charAt(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<Character, Integer> 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 == P.length()) {
return q;
}
}
return -1;
}
}
代码中,makeJumpTable调用用来构建跳转表,findSuffix用来查找最大的数值K, 使得P[1…k] 是字符串 Pq 的后缀,该调用有两层循环,所以复杂度是O( m2 ), makeJumpTable有两层循环,循环次数为O(m*| ∑ |), 所以makeJumpTable总的时间复杂度为O( m3 | ∑ |), 也就是说,构建跳转表的复杂度是:O( m3 | ∑ |)。
match依靠跳转表来判断,输入的字符串T是否包含字符串P,如果T的最后一个字符输入状态机后,从跳转表得到的状态的值等于P的长度m,那么表明T包含字符串P.具体的程序调试过程请参看视频。
我们只给出了算法的实现流程,算法的数学原理比较复杂,我们将在下一节详解。
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/171700.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...