[發(fā)明專利]字符串匹配方法、裝置及存儲(chǔ)介質(zhì)

在審

• 申請(qǐng)?zhí)枺?/td>: 202210244924.0
• 申請(qǐng)日: 2022-03-14
• 公開（公告）號(hào): CN114461865A
• 公開（公告）日: 2022-05-10
• 發(fā)明（設(shè)計(jì)）人: 羅小成;王春生
• 申請(qǐng)（專利權(quán)）人: 深圳希施瑪數(shù)據(jù)科技有限公司
• 主分類號(hào): G06F16/903
• 分類號(hào): G06F16/903
• 代理公司: 廣州三環(huán)專利商標(biāo)代理有限公司 44202
• 代理人: 賴妙旋

1.一種字符串匹配方法，其特征在于，所述方法包括：

獲取主串，所述主串包括M個(gè)字符，M為大于1的整數(shù)；

獲取模式串，所述模式串包括N個(gè)字符，N為小于M且大于1的正整數(shù)；

將所述主串和所述模式串對(duì)齊；

基于預(yù)設(shè)字符匹配原則，將所述模式串與所述主串中對(duì)應(yīng)的字符進(jìn)行匹配，所述預(yù)設(shè)字符匹配原則為雙向匹配原則或者末位字符優(yōu)先匹配原則；

在所述模式串與所述主串中對(duì)應(yīng)的字符匹配成功時(shí)，確認(rèn)所述模式串與所述主串之間匹配成功；

在所述模式串與所述主串中對(duì)應(yīng)的字符匹配失敗時(shí)，循環(huán)預(yù)設(shè)步驟，直到確認(rèn)所述模式串與所述主串之間匹配成功；

所述預(yù)設(shè)步驟包括：將所述模式串移動(dòng)至少N個(gè)字符的步長(zhǎng)；基于所述預(yù)設(shè)字符匹配原則，將移動(dòng)后的所述模式串與所述主串中對(duì)應(yīng)的字符進(jìn)行匹配。

2.根據(jù)權(quán)利要求1所述的方法，其特征在于，所述預(yù)設(shè)字符匹配原則為雙向匹配原則，所述將所述模式串與所述主串中對(duì)應(yīng)的字符進(jìn)行匹配，包括：

將所述模式串的首末字符與所述主串對(duì)應(yīng)的字符進(jìn)行匹配；

在所述模式串的首末字符與所述主串對(duì)應(yīng)的字符匹配失敗時(shí)，確認(rèn)所述模式串與所述主串之間匹配失敗；

在所述模式串的首末字符與所述主串對(duì)應(yīng)的字符匹配成功時(shí)，則將所述模式串的次首末字符與所述主串對(duì)應(yīng)的字符進(jìn)行匹配。

3.根據(jù)權(quán)利要求1所述的方法，其特征在于，所述預(yù)設(shè)字符匹配原則為末位字符優(yōu)先匹配原則，所述將所述模式串與所述主串中對(duì)應(yīng)的字符進(jìn)行匹配，包括：

檢測(cè)所述模式串的末位字符是否與相應(yīng)的所述主串的第一字符相匹配；

在所述模式串的末位字符與相應(yīng)的所述主串的第一字符不匹配時(shí)，確認(rèn)所述模式串與所述主串之間匹配失?。?/p>

在所述模式串的末位字符與相應(yīng)的所述主串的第一字符匹配時(shí)，則將所述模式串的次末字符與所述主串對(duì)應(yīng)的字符進(jìn)行匹配。

4.根據(jù)權(quán)利要求1-3任一項(xiàng)所述的方法，其特征在于，所述方法還包括：

確定N與M之間的第一比值；

在所述第一比值處于預(yù)設(shè)范圍時(shí)，執(zhí)行所述將所述主串和所述模式串對(duì)齊的步驟。

5.根據(jù)權(quán)利要求4所述的方法，其特征在于，在所述比值小于或等于所述預(yù)設(shè)范圍的下限值時(shí)，所述方法還包括：

確定所述模式串中每一字符在所述主串中的出現(xiàn)次數(shù)，得到X個(gè)出現(xiàn)次數(shù)；

確定所述X個(gè)出現(xiàn)次數(shù)的最小值；

獲取所述最小值對(duì)應(yīng)位置所述主串中的參考字符，得到P個(gè)參考字符，P為正整數(shù)；

根據(jù)所述P個(gè)參考字符將所述模式串進(jìn)行Q次移動(dòng)，得到Q個(gè)參考模式串，每一參考模式串中的至少一個(gè)字符與所述P個(gè)參考字符中的任一字符匹配，Q為大于或等于P的整數(shù)；

檢測(cè)所述Q個(gè)參考模式串中的每一字符是否與對(duì)應(yīng)位置所述主串中的字符均匹配；

在所述Q個(gè)參考模式串中的每一字符與對(duì)應(yīng)位置所述主串中的字符均匹配時(shí)，標(biāo)記出匹配位置，確認(rèn)在所述匹配位置時(shí)，確認(rèn)所述模式串與所述主串之間匹配成功。

6.根據(jù)權(quán)利要求5所述的方法，其特征在于，所述方法還包括：

確定X與N之間的第二比值；

在所述第二比值小于預(yù)設(shè)閾值時(shí)，執(zhí)行所述獲取所述最小值對(duì)應(yīng)位置所述主串中的參考字符的步驟。