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

2015-07-27周庆勋青岛广播电视大学技术装备处山东青岛266012

山东工业技术 2015年21期

关键词：字符串复杂度C语言

周庆勋（青岛广播电视大学、技术装备处,山东青岛 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])，直到匹配或比较结束为止。