[發明專利]一種模式匹配方法

無效

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

1.一種模式匹配方法，其特征在于，包括：

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

2.根據權利要求1所述的一種模式匹配方法，其特征在于，該方法對模式B、B’已經得到的部分匹配結果進行Q(r)值計算，以使模式B、B’交替向中間滑動。

3.根據權利要求2所述的一種模式匹配方法，其特征在于，所述的Q(r)值計算在下式條件時：

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

包括以下步驟：

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

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

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

d)結束。

4.根據權利要求2所述的一種模式匹配方法，其特征在于，所述的Q(r)值計算在下式條件時：

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

包括以下步驟：

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

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

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

d2)結束。