java自动机字符串匹配_4种字符串匹配算法:有限自动机(中)

接着上文(地址)，我们来聊一聊自动机算法(有限自动机字符串匹配算法)和KMP算法。

====#=有限自动机算法=#=====

关于有限自动机，网上的分析的资源，大部分都很笼统，算导上的知识点，全是数学公式，看的也会特别累。因此，打算从算导的第一题开始讲起。从习题入手，讲这个算法的思想。

例子：对模式 P = aabab构造出相应的字符串匹配自动机，并说明它在文本字符串T=aaababaabaababaab上的操作过程。

再讲这个例子之前，我们有必要先来了解一下自动机是什么意思？

有限自动机是什么意思？他是一个处理信息的简单机器，通过对文本字符串T进行扫描，找出模式P的所有出现的位置。它们只对每个文本字符检查一次，并且检查每个文本字符时所用的时间为常数。

我们来看看它的伪代码：

n=T.length

q= 0

for i = 1to n

q=ξ(q,T[i])if(q ==m)

print"..."

可以看出，他的时间复杂度为o(n),但是，这个匹配时间，并没有包括计算转移函数ξ的预处理时间。接下来，我们来做一做上面那个题目。

有限自动机分为5个组员(Q,q=0,A,∑,ξ)

我们假设：Q = {0,1,2,3,4,99} //99用来表示不会取得，如果等于99就跳出循环。

q:初始化为0

A={0} //代表了终点，这里只有一个终点

∑={a,b,c,d....x,y,z}

关于函数，我设计成这样：

aabab: {0* -> 1 -> 2 -> 3 -> 4 -> 0*}

1 #include

2 #include

3 #include

4 #include

5 intmain()6 {7 int a[] = { 1,2,0,0,0,8 0,0,0,0,0,9 0,0,0,0,0,10 0,0,0,0,0,11 0,0,0,0,0,0};12 int b[][5] ={13 /*, a, b*/

14 { 99,1,99 },//0

15 { 99,2,99 },//1

16 { 99,99,3 },//2

17 { 99,4,99 },//3

18 { 99,99,0 },//4

19

20 };21 char c[100];22 loop:23 while (std::cin >>c)24 {25 int str =strlen(c);26 for (int p = 0, i = 0;i < str;i++, p = 0)27 {28 int count =i;29 while (p < 99 && c[count] != 'r' && count

我们先创建一个数组a，因为字符串aabab只有a和b,所以初始化依次从1递增，其他为0。二维数据b,保存p值。

29 while (p < 99 && c[count] != 'r' && count

这段代码，用于获取p值。也就是ξ函数。也许，我们需要把他单独摘出来，要不然这个函数的执行时间为O(n*m)(展开下列函数，可看到和伪代码相同的c++代码),但事实上，他已经比BF算法好太多了。当然他也有弊病，如果预处理的时间太长，该怎么办？这是一个值得考虑的问题。换句话说，如果∑特别多，我们这里只有2个，建立的自动机时间也很长。我们有方法处理。

1 #include

2 #include

3 #include

4 #include

5

6 char c[100];7 int ppp(int &p, int &i, int &str);8

9 static int a[] = { 1,2,0,0,0,10 0,0,0,0,0,11 0,0,0,0,0,12 0,0,0,0,0,13 0,0,0,0,0,0};14 static int b[][5] ={15 /*, a, b*/

16 { 99,1,99 },//0

17 { 99,2,99 },//1

18 { 99,99,3 },//2

19 { 99,4,99 },//3

20 { 99,99,0 },//4

21 };22 intmain()23 {24

25

26 loop:27 while (std::cin >>c)28 {29 int str =strlen(c);30 for (int p = 0, i = 0;i < str;i++, p = 0)31 {32 int count =i;33 p =ppp(p,i,str);34 if (p == 0) {35 printf("YESn");36 gotoloop;37 }38 }39 }40 std::cout << "NO" <<:endl system>

44 int ppp(int &p, int &i,int &str)45 {46 int count =i;47 while (p < 99 && c[count] != 'r' && count

和伪代码格式相同的代码 O(n) 点击展开

当然，代码是有bug，如果输入的文本串中没有模式串，可能会显示不出来，我并没有考虑到这点。有待改善，但是为了理解算法本身，我就不再修改太多的东西，因为上面的代码已经比较清楚了。(好吧，其实是我比较懒,大半夜写代码，不容易啊)

我觉得要是理解上面的方法，和思想，再去看《算导》，应该就会稍微清楚一点了。但是《算导》上还是列出了一堆的数学公式。真心不是特别建议看这节，个人觉得会用就好，当然你能看下来都是好事。

练练手：地址 (这个更加复杂，因为∑有7个字符，以及6个字符串)

感言：这几天心特别躁，师兄研三了，找工作挺不容易的。阿里校招从3000减到了400(据说)，而且他是找c++方向的。工作不好找，因此，感慨算法是多么重要。好好学习算法，多做做项目，才是王道啊。

注：KMP留给下吧。欢迎交流。如果有什么错的地方，欢迎指正。