计算机工程与应用
計算機工程與應用
계산궤공정여응용
COMPUTER ENGINEERING AND APPLICATIONS
2014年
16期
104-108
,共5页
匹配%模式串%主串%入侵
匹配%模式串%主串%入侵
필배%모식천%주천%입침
matching%pattern string%main string%intrusion
经典字符串匹配算法的本质都是从左向右或者从右向左顺序进行字符匹配的，在主串中存在大量子串与模式串前缀或者后缀相同时效率较低，并且模式串最大右移长度为模式串长度。改进算法采用二分匹配字符串的方法，有效地避免了由主串中大量子串与模式串前缀相同或者后缀相同引起的无意义比较次数。模式串的移动距离根据改进的坏字符规则进行计算，增大了模式串的移动距离。实验结果表明，改进的字符串匹配算法可以有效地减少字符串的匹配次数和移动次数，达到了提高算法效率的目的。
經典字符串匹配算法的本質都是從左嚮右或者從右嚮左順序進行字符匹配的，在主串中存在大量子串與模式串前綴或者後綴相同時效率較低，併且模式串最大右移長度為模式串長度。改進算法採用二分匹配字符串的方法，有效地避免瞭由主串中大量子串與模式串前綴相同或者後綴相同引起的無意義比較次數。模式串的移動距離根據改進的壞字符規則進行計算，增大瞭模式串的移動距離。實驗結果錶明，改進的字符串匹配算法可以有效地減少字符串的匹配次數和移動次數，達到瞭提高算法效率的目的。
경전자부천필배산법적본질도시종좌향우혹자종우향좌순서진행자부필배적，재주천중존재대양자천여모식천전철혹자후철상동시효솔교저，병차모식천최대우이장도위모식천장도。개진산법채용이분필배자부천적방법，유효지피면료유주천중대양자천여모식천전철상동혹자후철상동인기적무의의비교차수。모식천적이동거리근거개진적배자부규칙진행계산，증대료모식천적이동거리。실험결과표명，개진적자부천필배산법가이유효지감소자부천적필배차수화이동차수，체도료제고산법효솔적목적。
The essence of classical string matching algorithms is sequential character matching which is always from left to right or from right to left. In the main string, if there are many substrings which have the same prefix or suffix with the pattern string, the algorithms are in the low efficiency. The maximum length for the shift is the length of the pattern string. The improved algorithm uses the two-string-separate-comparison method, effectively avoiding meaningless comparison times due to the same prefix or suffix of substrings and the pattern string. Since the algorithm calculates moving distance of the pattern string according to the improved bad character rule, it increases moving distance of the pattern string. The experimental results show that the improved string matching algorithm can effectively reduce the string matching times and moving times to improve the algorithm efficiency.
