字符串匹配Sunday算法
“Sunday算法是Daniel M.Sunday于1990年提出的字符串模式匹配。”
Sunday算法简介
字符串查找算法中,最著名的两个是KMP算法(Knuth-Morris-Pratt)和BM算法(Boyer-Moore)。两个算法在最坏情况下均具有线性的查找时间。但是在实用上,KMP算法并不比c库函数strstr()快多少,而BM算法则往往比KMP算法快上3-5倍(未经验证)。而Sunday算法比BM还要快,而且更易理解。Sunday算法的核心思想是:在匹配过程中,模式串并不被要求一定要按从左向右进行比较还是从右向左进行比较,它在发现不匹配时,算法能跳过尽可能多的字符以进行下一步的匹配,从而提高了匹配效率。