《Sunday算法详解及Java实现》由会员分享，可在线阅读，更多相关《Sunday算法详解及Java实现（5页珍藏版）》请在金锄头文库上搜索。
1、Sunday 算法详解及算法详解及 Java 实现实现一、一、 背景背景Sunday 算法是 Daniel M.Sunday 于 1990 年提出的字符串模式匹配。其效率在匹配随机的字符串时比其 他匹配算法还要更快。Sunday 算法的实现可比 KMP，BM 的实现容易太多。二、二、 原理原理Sunday 算法由 Daniel M.Sunday 在 1990 年提出，它的思想跟 BM 算法很相似：只不过 Sunday 算法是从前往后匹配，在匹配失败时关注的是文本串中参加匹配的最末位字符的下一 位字符。 如果该字符没有在模式串中出现则直接跳过，即移动位数 = 匹配串长度 + 1； 否则，其移动位
2、数 = 模式串中最右端的该字符到末尾的距离+1。三、三、 分析分析假设我们有如下字符串：假设我们有如下字符串： S = “LESSONS TEARNED IN SOFTWARE TE“; T = “SOFTWARE“;Sunday 算法的大致原理是：算法的大致原理是： 先从左到右逐个字符比较，以我们的字符串为例： （1）开始的时候，我们让 i = 0, 指向 S 的第一个字符; j = 0 指向 T 的第一个字符，分别为“L“和“S“，不 等；这个时候，Sunday 算法要求，找到位于 S 字串中位于 T 字符串后面的第一个字符，即下图中 m 所指向的字符“T“，在模式字符串 T 中从后向前查
3、找是否存在“T“。（2）可以看到下图中 k 指向模式串 T 的字符与 m 指向主串 S 的字符相等。（3）移动模式串 5 位，这时就将相等的字符对齐，让 j 再次指向模式串 T 的头一个字符“S“，相应地， 将 i 指向主串 S 对应的字符“N“。（4）再次比较 Si和 Tj，不等，这时再次寻找主串 S 中在模式串 T 后面的那个字符，m 和 k 所指向的 那个“E” 。（5）k 指向的模式串 T 字符与 m 指向的主串 S 字符“E”相等，因此再次移动模式串 1 位。（6）这时，主串 S 的 i 对应的字符是“S“，模式串 T 的 j 对应的子串字符也是“S“，i+, j+。（7）现在再次不
4、等， m 指向主串 S 的字符“D” 。（8）由于 m 指向主串 S 的字符“D“在模式串 T 中没有出现，所以直接移动模式串 9 位到主串 S 的字符 “D“后。i 指向主串 S 的空格，j 指向模式串 T 的“S” 。（9）再次比较 Si和 Tj，不等，这时再次寻找主串 S 中在模式串 T 后面的那个字符“W” ，m 和 k 所 指向的那个“W” 。（10）k 指向的模式串 T 字符与 m 指向的主串 S 字符“W”相等，因此再次移动模式串 4 位。（11）依次比较 Si和 Tj，直到比较模式串 T 最后一个字符“E” ，完全一致，查找成功。四、四、 完整代码完整代码程序代码如下：程序代码
5、如下：public class SundayTest /* 主函数* * param args 参数数组*/ public static void main(String args) / 定义原始数据String text = “LESSONS TEARNED IN SOFTWARE TE“; String pattern = “SOFTWARE“; System.out.println(“S:t“ + text);System.out.println(“T:t“ + pattern);/ 测试下一序号数组int next = next(pattern.toCharArray(); Syste
6、m.out.println(“下一序号数组:“);for (int i = 0; i S.length) return -1; / 获取下一序号数组int next = next(T);/ 遍历正文数组int delta = S.length - T.length; for (int i = 0; i = S.length) return -1; / 后移偏移距离(根据末位下一字符在模式字符串中的位置判断偏移距离)i += T.length - nextSi + T.length; / 返回查找失败return -1; 五、五、 运行结果运行结果运行结果如下运行结果如下:S:LESSONS TEARNED IN SOFTWARE TE T:SOFTWARE 下一序号数组:nextA:5 nextE:7 nextF:2 nextO:1 nextR:6 nextS:0 nextT:3 nextW:4 Sunday: 19 String: 19
