【导论】有穷自动机字符串匹配

作者:bibodeng 发布于:2012-10-23 8:51 Tuesday 分类:技术交流

有穷自动机
 
定义一个状态的集合Q,而一个状态q通过一个转移函数δ则可转移到另外一个状态q', 而自动有一个初始状态,还会有一个接受状态,到达了接受状态则说明该一系列的输入时符号该自动机所确定的模式。在编译原理的课上,接触了有穷自动机,而正则表达式和有穷自动自动机是等价的,程序设计语言的词法则可以用正则表达式来定义。可见,有穷自动机用来做字符匹配那是再合适不过了。
 
一个简单的...

阅读全文>>

标签: 算法 字符串匹配 DFA 有穷自动机

评论(0) 引用(0) 浏览(2733)

字符串匹配——RK算法

作者:bibodeng 发布于:2012-10-21 0:09 Sunday 分类:技术交流

【RK算法】

RK字符串匹配算法,在思想上是很简单易懂的,将字符串当成是一串数字,可以进行计算,若其值相等,那么字符串也便相等了。字符串视为数字有一个好处那就是减少了运算,在前面“朴素的字符串匹配”中,我们可以看到,如果按照一个个比对的办法将会花费 m *(n -m+1)的时间,但是如果是数字的话,从 T = “125025”中要匹配P = “25”则可以按如下过程进行计算:

点击查看原图

1、开始从1进行匹配...

阅读全文>>

标签: 算法 字符串匹配 RK

评论(0) 引用(1) 浏览(2155)

字符串匹配——朴素的字符串匹配

作者:bibodeng 发布于:2012-10-9 9:03 Tuesday 分类:编程技术

字符串匹配一直是一个很常见的问题,小到查找某个单词,大到DNA的检测。而字符串的匹配算法也很有意思,特别是有穷自动机和KMP算法,十分地精巧,令人惊叹,在有KMP之前,用的就是朴素的方法。

 

朴素的字符串匹配,就是遍历整个被检测字符串,然后一个个字符进行比对,如果不匹配则移到下一格,继续与模式进行匹配。导论里面说明: 被检测的字符串为目标字符串,而匹配的依据就是模式。

其匹配原理如下图所示:

点击查看原图

...

阅读全文>>

标签: 算法 字符串匹配 朴素

评论(0) 引用(2) 浏览(2279)

Powered by emlog 京ICP备16017775