[發(fā)明專利]一種模式匹配方法

無效

• 申請?zhí)枺?/td>: 200910195465.6
• 申請日: 2009-09-10
• 公開（公告）號: CN102024000A
• 公開（公告）日: 2011-04-20
• 發(fā)明（設計）人: 鄭駿;胡文心;蔡建華
• 申請（專利權）人: 華東師范大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 上海科盛知識產權代理有限公司 31225
• 代理人: 趙志遠

技術領域

本發(fā)明涉及串匹配技術，特別是涉及一種模式匹配方法。

背景技術

KMP匹配方法是串匹配中效率最高的方法，它充分利用模式信息，使得模式在跟主串匹配過程中主串的指針不回溯，從而具有較高的匹配速度，并在各種領域中有廣泛應用。然而，KMP方法仍存在著主串與模式多個相同字符重復比較的缺陷。

發(fā)明內容

本發(fā)明所要解決的技術問題就是為了克服上述現有技術存在的缺陷而提供一種模式匹配方法。

本發(fā)明的目的可以通過以下技術方案來實現：一種模式匹配方法，其特征在于，包括：

對匹配文本A設兩個指針，模式B和模式B’分別設一個指針，匹配文本A首端和模式B首端對齊，文本A末端和模式B’末端對齊；模式B指針起始位置為模式B的首端，模式B’指針起始位置為模式B’的末端，匹配文本A兩指針起始位置為文本首端和文本的末端；匹配過程中，模式B、模式B’分別和文本交替向中間匹配，當匹配過程中出現失配時，根據模式B、B’已經得到的部分匹配結果的將模式B、B’交替向中間滑動后繼續(xù)比較。

該方法對模式B、B’已經得到的部分匹配結果進行Q(r)值計算，以使模式B、B’交替向中間滑動。

所述的Q(r)值計算在下式條件時：

1(0)2+1≤i′≤A(0),]]>

包括以下步驟：

a1)i’＝B(0)，j’＝0，Q(B(0))＝0；

b1)若i’＝1，則執(zhí)行步驟d1；否則，執(zhí)行步驟c1；

c1)若j’＝B(0)或B(i’)＝B(j’)，則i’＝i’-1，j’＝j’-1，Q(i’)＝j’，執(zhí)行步驟b1；否則，j’＝Q(j’)，執(zhí)行步驟c1；

d)結束。

所述的Q(r)值計算在下式條件時：

1≤i≤A(0)2,]]>

包括以下步驟：

a2)i＝1，j＝0，Q(1)＝0；

b2)若i＝m，則執(zhí)行步驟d2；否則，執(zhí)行步驟c2；

c2)若j＝0或(B(i)＝B(j))，則j＝j+1，i＝i+1，Q(i)＝j，執(zhí)行步驟b2；否則，j＝Q(j)，執(zhí)行步驟c2；

d2)結束。

與現有技術相比，本發(fā)明避免了字符的重復匹配，減少了比較次數，提高了匹配效率。

具體實施方式

下面對本發(fā)明作進一步說明。

一種模式匹配方法，包括：

對匹配文本A設兩個指針，模式B和模式B’分別設一個指針，匹配文本A首端和模式B首端對齊，文本A末端和模式B’末端對齊；模式B指針起始位置為模式B的首端，模式B’指針起始位置為模式B’的末端，匹配文本A兩指針起始位置為文本首端和文本的末端；匹配過程中，模式B、模式B’分別和文本交替向中間匹配，當匹配過程中出現失配時，根據模式B、B’已經得到的部分匹配結果的將模式B、B’交替向中間滑動后繼續(xù)比較。

該方法對模式B、B’已經得到的部分匹配結果進行Q(r)值計算，以使模式B、B’交替向中間滑動。

所述的Q(r)值計算在下式條件時：