正文

字符串模式匹配算法sunday算法

王景迁  王景迁  2022-09-24  357

关键词：

　　Sunday算法是Daniel M.Sunday于1990年提出的字符串模式匹配算法。相对比较KMP和BM算法而言，简单了许多。

　　Sunday算法的思想类似于BM算法中的坏字符思想，有点像其删减版。差别在于Sunday算法在失配之后，是取目标串中当前和模式串匹配的部分后面一个位置的字符来做坏字符匹配。其时间复杂度和BM算法差不多，平均性能的时间复杂度也为O(n)。Sunday算法的位移比BM算法更大，所以Sunday算法的效率比BM算法更高，在匹配随机字符串时效率比其他匹配算法快。最差情况的时间复杂度为O(n * m)，考虑如下目标串：baaaabaaaabaaaabaaaa，在里面搜索aaaaa，没有匹配位置。如果用Sunday算法，坏字符大部分都是a，而模式串中又全部都是a，所以在大部分情况下，失配后模式串只能往右移动1位。

匹配原理：从前往后匹配，如果不匹配，则根据母串S对齐部分的最后一个字符的下一个字符进行判断：如果该字符出现在模板串T中，则选择最右出现的位置进行对齐；否则，直接跳过该匹配区域。

　　母串S：s e a r c h s u b s t r i n g

　　模板串T：s u b s t r i n g

　　开始匹配（第1个字符）：

　　s e a r c h s u b s t r i n g

　　s u b s t r i n g

　　继续下一字符匹配（第2个字符）：

　　s e a r c h s u b s t r i n g

　　s u b s t r i n g

　　出现不匹配情况，查找母串对齐部分的最后一个字符的下一个字符s。在T中，字符s出现两次，按照原理，选择最右位置出现的s进行对齐，那么可以得到：

　　s e a r c h s u b s t r i n g

　　 s u b s t r i n g

　　假设母串S为：s e a r c h s u b z t r i n g

　　那么当匹配到上述情况时，字符z在T中没有出现，那么就可以得到下面的情况：

　　s e a r c h s u b z t r i n g

　　　　　　 s u b s t r i n g

　　这就是其原理的两种情况。

　　Java语言实现（s表示母串，t表示模板串）：

 1 public class Sunday {
 2     // 数组容量可变，依字符范围而定
 3     private static final int MAX_SIZE = 65536;
 4     // 匹配失败时的移动距离
 5     private static final int[] MOVE_LENGTH = new int[MAX_SIZE];
 6     
 7     // 设置移动距离
 8     private static void setMoveLength(int tLen, String t) {
 9         int tLenPlusOne = tLen + 1;
10         // 默认子串中的任何字符不出现在母串中，移动距离是子串长度 + 1
11         for (int i = 0; i < MAX_SIZE; i++) {
12             MOVE_LENGTH[i] = tLenPlusOne;
13         }
14         
15         // 确定母串匹配部分最后一个字符的下一个字符在子串中最右出现的位置
16         for (int i = 0; i < tLen; i++) {
17             MOVE_LENGTH[t.charAt(i)] = tLen - i;
18         }
19     }
20     
21     // 顺序查找指定子串在指定母串中首次出现的位置
22     public static int indexOf(String s, String t) {
23         // 如果两个字符串至少有一个是null
24         if (s == null || t== null) {
25             return -1;
26         }
27         
28         // 获取字符串长度
29         int sLen = s.length();
30         int tLen = t.length();
31         // 设置移动距离
32         setMoveLength(tLen, t);
33         
34         // i是母串遍历下标
35         for (int i = 0; i < sLen; ) {
36             // j是子串遍历下标
37             int j = 0;
38             // 不断匹配字符
39             while (j < tLen && i + j < sLen && s.charAt(i + j) == t.charAt(j)) {
40                 j++;
41             }
42             
43             // 如果查找成功
44             if (j == tLen) {
45                 return i;
46             }
47             
48             // 向右移动距离最小是1，i + tLen是匹配时最后一个字符下标
49             // 如果该下标越界，则查找失败
50             if (i + tLen >= sLen) {
51                 return -1;
52             }
53             
54             // 右移对齐
55             i += MOVE_LENGTH[s.charAt(i + tLen)];
56         }
57         
58         // 查找失败
59         return -1;
60     }
61     
62     public static void main(String[] args) {
63         String s = "searchsubstring";
64         String t = "substring";
65         System.out.println(indexOf(s, t));
66     }
67 
68 }

　　结果：

　　参考资料

　　【模式匹配】之 —— Sunday算法

　　数据结构与算法系列----Sunday算法详解

BF、KMP、BM、Sunday算法讲解

sunday算法模板

Sunday是一个线性字符串模式匹配算法。算法的概念如下：Sunday算法是DanielM.Sunday于1990年提出的一种字符串模式匹配算法。其核心思想是：在匹配过程中，模式串并不被要求一定要按从左向右进行比较还是从右向左进行比较，它在... 查看详情

字符串匹配之sunday算法

Sunday算法不像KMP算法那么复杂，但是效率又比较高，在KMP之上，下面简单介绍Sunday算法及其实现。Sunday算法由DanielM.Sunday在1990年提出，它的思想跟BM算法很相似：只不过Sunday算法是从前往后匹配，在匹配失败时关注的是文本串中... 查看详情

sunday算法

Sunday算法是DanielM.Sunday于1990年提出的字符串模式匹配。其核心思想是：在匹配过程中，模式串发现不匹配时，算法能跳过尽可能多的字符以进行下一步的匹配，从而提高了匹配效率。　　核心思想：在匹配过程中，... 查看详情

字符串匹配的sunday算法

...day算法核心思想：启发式移动搜索步长！SUNDAY算法描述：字符串查找算法中，最著名的两个是KMP算法（Knuth-Morris-Pratt)和BM算法（Boyer-Moore)。这里介绍一种比BM算法更快一些的sunday查找算法。例如我们要在"substringsearchingalgorithm"查... 查看详情

sunday算法

一.应用：　　同样的，sunday算法也是在一个字符串中查找另一个字符串出现的首地址，是DanielM.Sunday于1990年提出的，从销量上讲，Sunday>BM>KMP,是这类问题的最优解。在实用上，KMP算法并不比最简单的c库函数strstr()快多少，而... 查看详情

sunday算法

Sunday算法2017-08-30Sunday算法是DanielM.Sunday于1990年提出的字符串模式匹配。并不知道他是谁(来自百度)Q:那么Sunday是干什么的?s:吾看他能在期望O(n)的时间里知道在串S1中S2出现了几次xQ:那他是怎么实现的呢?s:就是在字符串发生失配的... 查看详情

字符串匹配常见算法（bf，rk，kmp，bm，sunday）

　　今日了解了一下字符串匹配的各种方法。　　并对sundaysearch算法实现并且单元。字符串匹配算法，是在实际工程中经常遇到的问题，也是各大公司笔试面试的常考题目。此算法通常输入为原字符串（string）和子串（pattern）... 查看详情

字符串匹配算法(代码片段)

字符串匹配算法原文摘录：https://www.cnblogs.com/gaochundong/p/string_matching.html首先是一系列概念定义：文本Text:是一个长度为n的数组T[1..n] (??这里第一位置索引是数字1)模式Pattern:是一个长度为m的数组P[1..m], 并且m<=n.T和P... 查看详情

字符串匹配算法(代码片段)

文章目录1字符串匹配算法1.1暴力检索BF1.2KMP算法1.2.1核心思想1.2.2部分匹配表1.2.3计算：向后移动的位数1.2.4时间复杂度1.2.5算法实现1.3BM算法1.3.1相关概念1.3.1.1坏字符：坏字符有两种情况：1.3.1.2好后缀1.3.2BM算法全过程1... 查看详情

字符串模式匹配kmp算法

字符串模式匹配指的是，找出特定的模式串在一个较长的字符串中出现的位置。朴素的模式匹配算法很直观的可以写出下面的代码，来找出模式串在一个长字符串中出现的位置。/*朴素的模式匹配算法功能：字符串的模式匹配参... 查看详情

常用算法3-字符串查找/模式匹配算法（bf&kmp算法）

...linux是如何在浩如烟海的文本中正确匹配到我们所需要的字符串呢？这就牵扯到了模式匹配算法！1.模式匹配什么是模式匹配呢？模式匹配，即子串P(模式串)在主串T(目标串)中的定位运算，也称串匹配假设我们有两个字符串：T(Tar... 查看详情

字符串多模式匹配：ac算法

　　早在1975年贝尔实验室的两位研究人员AlfredV.Aho和MargaretJ.Corasick就提出了以他们的名字命名的高效的匹配算法—AC算法。该算法几乎与《KMP算法》同时问世。与KMP算法相同，AC算法时至今日仍然在模式匹配领域被广泛应用。... 查看详情

字符串模式匹配算法bm

...指目标串长度，m指模式串长度。BM算法是比KMP算法更快的字符串模式匹配算法。　　KMP算法从左向右比较，通过失配时已匹配的字符信息来确定下一次匹配时模式串的起始位置。BM算法从右向左比较，运用了两种启发式规则：坏... 查看详情

正则引擎在数据包匹配中的工程分析

匹配常见的通用匹配算法有字符串匹配和正则匹配。字符串匹配常见的算法有Boyer-Moore算法、orspool算法、unday算法、MP算法、R算法、AC自动机。Boyer-Moore、Horspool、Sunday算法都是基于后缀数组的匹配算法，区别在于移动的方式不一... 查看详情

kmp算法字符串匹配算法(代码片段)

简介字符串的模式匹配是对字符串的基本操作之一，广泛应用于生物信息学、信息检索、拼写检查、语言翻译、数据压缩、网络入侵检测等领域，如何简化其复杂性一直是算法研究中的经典问题。字符串的模式匹配实质上就是寻... 查看详情

算法基础-朴素模式匹配算法、kmp模式匹配算法

参考技术A假设我们要从主字符串goodgoogle中匹配子字符串google朴素模式匹配算法就是通过从主字符的头部开始一次循环匹配的字符串的挨个字符如果不通过则主字符串头部位置遍历位置+1在依次遍历子字符串的字符匹配过程主字... 查看详情

模式匹配算法(代码片段)

1、基本概念：　　目标串：s　　模式串：t　　模式串第j个元素：t[j] 2、BF算法：　　通过将目标串S的第一个字符与模式串T的第一个字符进行匹配，若相等，则继续比较S的第二个字符和 T的第二个字符；若不相等，则比... 查看详情

kmp算法模式串匹配

转载：字符串匹配 kmp算法查看详情