Sunday 算法

Sunday 算法是一种基于跳跃思想的单模式字符串匹配算法。它与博耶-穆尔算法同源,但在失配时把注意力放在主串中紧邻当前匹配窗口之后的那个字符上,以此计算模式串应向右滑动的距离,常能实现较大跨度的跳跃。

概述

该算法由丹尼尔·桑迪(Daniel Sunday)于1990年提出。它的匹配尝试从左到右比较,一旦发现不匹配,便查看主串中位于窗口右端下一位的字符。由于无论如何滑动,该字符都必须参与下一次匹配,算法据它在模式串中的位置决定跳跃量,思路直观且实现简单。

核心原理

• 关键字符:失配后考察主串中当前窗口之后紧邻的那个字符。
• 移动规则:若该字符在模式串中出现,则对齐其最右出现位置;若不出现,则整体跳过。
• 预处理:提前记录模式串中每个字符最靠右的位置,构成移动表。
• 平均高效:多数情况下每次可跳过较多字符,平均性能优于逐位比较的朴素匹配。

应用场景

Sunday 算法适用于文本编辑器查找、日志检索、简单模式匹配等对实现简洁性有要求的场合。它常与 KMP、博耶-穆尔等算法一同被讨论,作为字符串匹配教学中的实用范例,也用于一些轻量级的搜索工具中。

常见问题

问:Sunday 算法比博耶-穆尔快吗?答:两者思路相近,Sunday 因利用窗口后一位字符,平均跳跃往往更大、实现更简单;但博耶-穆尔有更完善的最坏情况分析,实际优劣依数据而定。

问:Sunday 算法最坏情况如何?答:在特意构造的重复数据下,它可能退化到主串长度乘模式串长度的量级,因此对最坏性能敏感的场景应考虑有线性保证的算法。