基于散列函数的模式匹配算法

周庆勋（青岛广播电视大学、技术装备处,山东 青岛 266012）

基于散列函数的模式匹配算法

周庆勋
（青岛广播电视大学、技术装备处,山东 青岛 266012）

本文简要介绍了利用散列函数进行模式匹配的原理，散列函数的构造，给出了基于散列函数的模式匹配算法。

散列函数；模式匹配；算法

0 引言

模式匹配是数据结构中字符串的一种基本运算，给定一个子串，要求在某个字符串中找出与该子串相同的所有子串，这就是模式匹配。

假设P是给定的子串，T是待查找的字符串，要求从T中找出与P相同的所有子串，这个问题成为模式匹配问题。P称为模式，T称为目标。如果T中存在一个或多个模式为P的子串，就给出该子串在T中的位置，称为匹配成功；否则匹配失败。

模式匹配算法是文本处理领域中比较重要的算法，一个简单、高效率的模式匹配算法对提高和模式匹配有关的软件的效率有很大帮助，本文介绍一种基于散列函数的模式匹配算法，该算法简单，易于理解且具有较高的效率。

1 原理

令模式记为x=x[0..m-1]，长度为m，文本串记为y=y[0..n-1]，长度为n。令算列函数：hash(x[0..m-1]=x[0]*2m-1+x[1]*2m-2+…+x[m-1]) mod q(式中q为系统最大整型值)

该散列函数具有以下特点：

1.1 易于计算

1.2 易于从hash(y[i，i+m-1])计算hash(y[i+1，i+m])

hash(y[i+1，i+m])=(( hash(y[i，i+m-1])-y[i]*2m-1)*2+y[i+m]) mod q

为提高运算速度，乘以2的操作可通过左移1位实现，对于给定的模式x，2m-1是一个常数。在一个模式匹配的过程中，若模式x在文本y中出现的位置为i，则必定hash(x)=hash(y[i，i+m-1])，但要注意，hash(x)=hash(y[i，i+m-1])时，x[0..m]和y[i，i+m-1]未必完全匹配。因此，模式匹配的过程就是hash(x)=hash(y[i，i+m-1])（其中i=0，1，…，n-m）逐个比较的过程，若hash(x)和hash(y[i，i+m-1])，则将x[0..m]和y[i，i+m-1]逐字符比较，若完全相等，则模式匹配的位置为i，否则不匹配，继续比较hash(x)和hash(y[i+1，i+m])，直到匹配或比较结束为止。

2 算法

下面给出用C语言函数描述的具体算法

3 结语

在预期情况下该算法的时间复杂度为O(n+m)，在最坏情况下，该算法的时间复杂度为O（n*m）。尽管该算法在效率上不是最好，但算法简单，易于理解，在对时间复杂度要求不是很苛刻的环境下，还是一个简单高效的模式匹配算法。

[1]罗大光,郝玉洁,刘乃琦.一种非常快速的字符串匹配算法[J].电子科技大学学报,2005,34(06):802-805.

[2]严大治.字符串匹配算法比较与分析[J].计算机光盘软件与应用,2013(02):138-140.

[3]严蔚敏，吴伟民.数据结构（C语言版）[M].北京:清华大学出版社，1996:79-80.

10.16640/j.cnki.37-1222/t.2015.21.196