支持模式串动态更新的多模式匹配Karp-Rabin算法

来源：计算机工程与应用杂志2017年第4期北京时间：

作者：王 歧1，2，3，卢毓海1，3，刘 洋1，3，刘燕兵1，3，谭建龙1，3，孙 波4

单位：1.中国科学院 信息工程研究所，北京 100093；2.中国科学院大学，北京 100049；3.信息内容安全技术国家工程实验室，北京 100093；4.国家计算机网络应急技术处理协调中心，北京 100029

摘要：多模式匹配算法是网络监测和内容过滤系统的核心算法，但是现有的多模式匹配算法无法实现高并发下动态更新模式串的功能。通过改进Karp-Rabin 算法，实现了多模式字符串匹配技术，实验表明多模式Karp-Rabin算法具有良好的性能。随后在多模式Karp-Rabin 算法的基础上进一步改进，使其在高并发情况下能够支持模式串动态增删功能。实验表明该算法在单个线程不断更新的条件下，随着扫描线程个数的增加，搜索速度能够保持线性增长。

关键词：多模式匹配,Karp-Rabin算法,动态更新,入侵检测系统,多线程