一种基于分段匹配的字符串匹配算法

摘要

Existing algorithms have bigger dependence to the pertinence between text and patterns, to avoid this, a string matching algorithm named SM based on segmenting is proposed. This algorithm cuts text first and then matches the patterns, all with the aid of special characters, and it is insensitive to the content and length of patterns in matching course. It is proved that SM algorithm does behave steadily in performance by analysing it and comparing it through experiment both with the classical algorithms, especially in the circumstance of multi-pattern strings matching,SM algorithm performs better than Wu-Manber algorithm in speed and space cost.%针对已有算法对文本和模式的相关性依赖较大,提出一种基于分段的字符串匹配算法——SM.该算法利用特殊字符将文本先分段再匹配,且匹配过程对模式内容和长度不敏感.通过将SM算法与经典算法进行分析和实验对比,证明SM算法性能稳定,特别是在多模式字符串匹配情况下,SM算法具有比Wu-Manber算法更快的速度和更小的空间消耗.