[發(fā)明專利]一種字符串匹配方法及裝置

在審

• 申請?zhí)枺?/td>: 201310728044.1
• 申請日: 2013-12-25
• 公開（公告）號: CN104750683A
• 公開（公告）日: 2015-07-01
• 發(fā)明（設(shè)計）人: 任眾;李晟;范曉暉;薛峰;劉俊萍
• 申請（專利權(quán)）人: 中國移動通信集團(tuán)公司
• 主分類號: G06F17/30
• 分類號: G06F17/30;G06F17/22
• 代理公司: 北京同達(dá)信恒知識產(chǎn)權(quán)代理有限公司 11291
• 代理人: 郭潤湘

技術(shù)領(lǐng)域

本發(fā)明涉及模式匹配領(lǐng)域，尤其涉及一種字符串匹配方法及裝置。

背景技術(shù)

字符串匹配是在一個大的目標(biāo)字符串?dāng)?shù)據(jù)庫中搜索出某個給定模式字符串位置的過程。字符串匹配應(yīng)用較廣泛，例如：在入侵檢測系統(tǒng)中，為了對網(wǎng)絡(luò)系統(tǒng)的運行狀態(tài)進(jìn)行監(jiān)視，發(fā)現(xiàn)各種攻擊企圖、攻擊行為或者攻擊結(jié)果，保證系統(tǒng)資源的機(jī)密性和可用性，需要對獲取的網(wǎng)絡(luò)數(shù)據(jù)包進(jìn)行檢測是否存在入侵的非法數(shù)據(jù)，首先將針對一類數(shù)據(jù)包的所有已知的入侵行為的模式字符串分別放在模式字符串庫中，對入侵的非法數(shù)據(jù)的檢測，可以通過字符串匹配，確定獲取的網(wǎng)絡(luò)數(shù)據(jù)包的字符串中是否存在模式字符串庫中的模式字符串，如果存在，表示存在入侵行為。

目前，現(xiàn)有的字符串匹配的常用的方法如下：

針對一個特定的模式字符串，從待匹配的目標(biāo)字符串的第一個字符開始，逐個比對連續(xù)的字符與模式字符串的位置相同的字符是否相同，并且，在比對的過程中，當(dāng)目標(biāo)字符串與模式字符串中的前一對字符相同時，再比對下一對字符是否相同，如果目標(biāo)字符串與模式字符串中的最后一對字符相同，即目標(biāo)字符串與模式字符串中的每對字符均相同，表示該模式字符串在該目標(biāo)字符串中存在，如果在比對的過程中，目標(biāo)字符串與模式字符串中的一對字符不相同，則確定不相同的該對字符中的屬于目標(biāo)字符串的字符，并從目標(biāo)字符串的該字符開始，采用與上述相同的方式，逐個比對連續(xù)的字符與模式字符串的位置相同的字符是否相同，直到確定該模式字符串在該目標(biāo)字符串中存在，或者將目標(biāo)字符串的所有字符比對完畢。

例如：目標(biāo)字符串A=ababae，模式字符串B=abae，采用上述方案，將模式字符串B與目標(biāo)字符串A的字符逐個進(jìn)行比對，當(dāng)比對到第四個字符時，e≠b，則從目標(biāo)字符串A的第四個字符b開始繼續(xù)與模式字符串B的每個字符逐個進(jìn)行比對。

上述字符串匹配方法，由于當(dāng)目標(biāo)字符串與模式字符串中的一對字符不相同時，確定不相同的該對字符中的屬于目標(biāo)字符串的字符，并從目標(biāo)字符串的該字符開始，繼續(xù)逐個比對連續(xù)的字符與模式字符串的位置相同的字符是否相同，以上述字符串A、B為例，當(dāng)模式字符串B與目標(biāo)字符串A的第四個字符比對不相同時，從目標(biāo)字符串A的第四個字符開始，繼續(xù)逐個比對連續(xù)的字符與模式字符串的位置相同的字符是否相同，但如果從目標(biāo)字符串的第三個字符開始逐個比對連續(xù)的字符與模式字符串的位置相同的字符，則目標(biāo)字符串A與模式字符串B中的每對字符均相同，因此這種字符串匹配方法的準(zhǔn)確度低。

發(fā)明內(nèi)容

本發(fā)明實施例提供一種字符串匹配方法及裝置，用以解決現(xiàn)有技術(shù)中存在字符串匹配方法的準(zhǔn)確度低的問題。

本發(fā)明實施例提供一種字符串匹配方法，包括：

確定模式字符串首字符在待匹配的目標(biāo)字符串中存在的各位置；

當(dāng)所述各位置中存在滿足預(yù)設(shè)條件的位置時，確定所述模式字符串在所述目標(biāo)字符串中存在，其中，對于滿足預(yù)設(shè)條件的位置，從所述目標(biāo)字符串的滿足預(yù)設(shè)條件的該位置的字符開始，所述目標(biāo)字符串與所述模式字符串中的每對位置相同的字符均相同。

采用本發(fā)明實施例提供的方法，由于在對待匹配的目標(biāo)字符串中確定是否存在模式字符串時，首先確定模式字符串首字符在待匹配的目標(biāo)字符串中存在的各位置，避免了目標(biāo)字符串中與模式串首字符相同的字符位置可能未進(jìn)行字符比對的問題，提高了字符串匹配的準(zhǔn)確度。

進(jìn)一步的，確定一個位置是否滿足所述預(yù)設(shè)條件，具體包括：

針對該位置，比對從所述目標(biāo)字符串的該位置的字符開始連續(xù)的字符與所述模式字符串的位置相同的字符是否相同；

當(dāng)從所述目標(biāo)字符串的該位置的字符開始，所述目標(biāo)字符串與所述模式字符串中的每對位置相同字符均相同，確定該位置滿足所述預(yù)設(shè)條件。

進(jìn)一步的，確定一個位置是否滿足所述預(yù)設(shè)條件，具體包括：

針對該位置，比對從所述目標(biāo)字符串的該位置的下一個字符開始連續(xù)的字符與所述模式字符串的第二個字符開始位置相同的字符是否相同；

當(dāng)從所述目標(biāo)字符串的該位置的下一個字符開始，所述目標(biāo)字符串與所述模式字符串中第二個字符串開始的每對位置相同的字符均相同，確定該位置滿足所述預(yù)設(shè)條件。

進(jìn)一步的，確定模式字符串首字符在待匹配的目標(biāo)字符串中存在的各位置，具體包括：

將模式字符串首字符與待匹配的目標(biāo)字符串中的每個字符進(jìn)行比對；

將所述目標(biāo)字符串中與所述首字符相同的字符所在的各位置，確定為所述首字符在所述目標(biāo)字符串中存在的各位置。

本發(fā)明實施例還提供了一種入侵檢測方法，包括：