周慶勛（青島廣播電視大學(xué)、技術(shù)裝備處,山東 青島 266012）

基于散列函數(shù)的模式匹配算法

周慶勛
（青島廣播電視大學(xué)、技術(shù)裝備處,山東 青島 266012）

本文簡要介紹了利用散列函數(shù)進(jìn)行模式匹配的原理，散列函數(shù)的構(gòu)造，給出了基于散列函數(shù)的模式匹配算法。

散列函數(shù)；模式匹配；算法

0 引言

模式匹配是數(shù)據(jù)結(jié)構(gòu)中字符串的一種基本運(yùn)算，給定一個(gè)子串，要求在某個(gè)字符串中找出與該子串相同的所有子串，這就是模式匹配。

假設(shè)P是給定的子串，T是待查找的字符串，要求從T中找出與P相同的所有子串，這個(gè)問題成為模式匹配問題。P稱為模式，T稱為目標(biāo)。如果T中存在一個(gè)或多個(gè)模式為P的子串，就給出該子串在T中的位置，稱為匹配成功；否則匹配失敗。

模式匹配算法是文本處理領(lǐng)域中比較重要的算法，一個(gè)簡單、高效率的模式匹配算法對提高和模式匹配有關(guān)的軟件的效率有很大幫助，本文介紹一種基于散列函數(shù)的模式匹配算法，該算法簡單，易于理解且具有較高的效率。

1 原理

令模式記為x=x[0..m-1]，長度為m，文本串記為y=y[0..n-1]，長度為n。令算列函數(shù)：hash(x[0..m-1]=x[0]*2m-1+x[1]*2m-2+…+x[m-1]) mod q(式中q為系統(tǒng)最大整型值)

該散列函數(shù)具有以下特點(diǎn)：

1.1 易于計(jì)算

1.2 易于從hash(y[i，i+m-1])計(jì)算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

為提高運(yùn)算速度，乘以2的操作可通過左移1位實(shí)現(xiàn)，對于給定的模式x，2m-1是一個(gè)常數(shù)。在一個(gè)模式匹配的過程中，若模式x在文本y中出現(xiàn)的位置為i，則必定hash(x)=hash(y[i，i+m-1])，但要注意，hash(x)=hash(y[i，i+m-1])時(shí)，x[0..m]和y[i，i+m-1]未必完全匹配。因此，模式匹配的過程就是hash(x)=hash(y[i，i+m-1])（其中i=0，1，…，n-m）逐個(gè)比較的過程，若hash(x)和hash(y[i，i+m-1])，則將x[0..m]和y[i，i+m-1]逐字符比較，若完全相等，則模式匹配的位置為i，否則不匹配，繼續(xù)比較hash(x)和hash(y[i+1，i+m])，直到匹配或比較結(jié)束為止。

2 算法

下面給出用C語言函數(shù)描述的具體算法

3 結(jié)語

在預(yù)期情況下該算法的時(shí)間復(fù)雜度為O(n+m)，在最壞情況下，該算法的時(shí)間復(fù)雜度為O（n*m）。盡管該算法在效率上不是最好，但算法簡單，易于理解，在對時(shí)間復(fù)雜度要求不是很苛刻的環(huán)境下，還是一個(gè)簡單高效的模式匹配算法。

[1]羅大光,郝玉潔,劉乃琦.一種非常快速的字符串匹配算法[J].電子科技大學(xué)學(xué)報(bào),2005,34(06):802-805.

[2]嚴(yán)大治.字符串匹配算法比較與分析[J].計(jì)算機(jī)光盤軟件與應(yīng)用,2013(02):138-140.

[3]嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）[M].北京:清華大學(xué)出版社，1996:79-80.

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