Sunday算法介绍及Java实现

前言

最初想写这篇文章的原因是在LeetCode上看到了一道实现strStr函数的题:

实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在,则返回 -1。

题目要求实现一个函数:

public int strStr(String haystack, String needle) 

这个函数的两个参数名分别为haystack和needle,可能有人会疑惑为什么要用这么两个看着不相关的单词作为参数名,这里稍微解释下:英语有个口语叫"It's a needle in a haystack",直接意思就是草垛寻针,也就是大海捞针之意。一方面传达了我们这个函数的功能,同时可能也想凸现一下这个操作的复杂度吧,老外有时候就是喜欢整一些黑色幽默。
因此,在后文的介绍里,haystack就是操作源数据,needle就是我们要去搜索的目标。

其实有很多算法可以来实现字符串查找,暴力的BF算法,经典的KMP算法,BM算法,Sunday算法等等,就效率和实现难度上来说,Sunday算法应该是性价比最高的,效率高,容易理解,实现也比较简单。

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

下面我们通过示例来理解一下Sunday算法的工作原理:

示例原理

Sunday采用模式匹配的思想,匹配失败时,选择haystack中参加匹配的最末尾字符的后一位字符作为参照字符,如果该字符在needle串中有出现,则将needle串中最后出现该字符的位置与参照字符位置对齐继续比较,否则直接跳过该匹配区域,从参照字符的下一位重新开始比较。
OK,这一段实在太长,可能不太好理解,简单粗暴,来举个例子:

说明:

场景一:对照字符在needle中存在

首先从前往后对needle和haystack串中参与比较的子串here进行字符比较,发现第一个字符匹配失败,则找到haystack参与比较的子串末尾字符的后一个字符e作为参照字符,然后我们在needle串中从后往前找到字符e,然后将两者位置对齐,如下图所示:

场景二:对照字符在needle中不存在

对齐后我们继续对比needle串和haystack中新参与比较的子串ere e,发现依然不匹配。我们找到比较子串的后一个字符v作为参照字符,寻找v在needle串中最后出现的位置,显然needle串中并不存在字符v,这种情况下,我们可以直接将主串游标跳到字符v后继续下一轮比较。

重新对齐后,比较发现依然不匹配,继续找到下一个对照字符h,h在needle串中有出现,满足上述场景一的条件,则找到h在needle串中最后出现的位置与参照字符对齐,继续比较,发现匹配成功。

代码实现

该算法的Java实现

    public int Sunday(String haystack, String needle) {
        int hayLen = haystack.length();
        int nLen = needle.length();

        int i = 0;//haystack串的游标索引
        int j = 0;// needle串的游标索引

        // haystack剩余字符少于needle串时跳过比较
        while (i <= hayLen - nLen) {
            // 将needle串与haystack串中参与比较的子串进行逐个字符比对
            while (j < nLen && haystack.charAt(i + j) == needle.charAt(j)) {
                j++;
            }

            // 如果j等于needle串的长度说明此时匹配成功,可以直接返回此时主串的游标索引
            if (j == nLen) {
                return i;
            }

            // 不匹配时计算需要跳过的字符数,移动主串游标i
            if (i < hayLen - nLen) {
                // 对照字符在needle串存在,则需要跳过的字符数为从对照字符在needle串中最后出现的位置起剩余的字符个数
                // 不存在则跳过的字符数为needle串长度+1,也就是代码nLen-(-1)的情况
                i += (nLen - lastIndex(needle, haystack.charAt(i + nLen)));
            } else {
                return -1;
            }
            // 每次比较之后将needle游标置为0
            j=0;
        }

        return -1;
    }
    
    public int lastIndex(String str, char ch) {
        // 从后往前检索
        for (int j = str.length() - 1; j >= 0; j--) {
            if (str.charAt(j) == ch) {
                return j;
            }
        }
        return -1;
    }
    

实际环境中可以根据needle串的约束对needle串进行预处理,提前建立好索引,提高查找效率。

总结

通过上文介绍不难发现,Sunday算法在处理重复字符少的场景效率会很高,因为每次都可以跳过比较多的字符,很大程度的减少了比较次数,综合来说,Sunday算法的平均时间复杂度为O(n),最差情况的时间复杂度为O(n * m).

个人博客原文,转载请注明出处,如有错误的地方请留言给我更正,谢谢!

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 219,188评论 6 508
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 93,464评论 3 395
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 165,562评论 0 356
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 58,893评论 1 295
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 67,917评论 6 392
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 51,708评论 1 305
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 40,430评论 3 420
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 39,342评论 0 276
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 45,801评论 1 317
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,976评论 3 337
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 40,115评论 1 351
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 35,804评论 5 346
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 41,458评论 3 331
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 32,008评论 0 22
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 33,135评论 1 272
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 48,365评论 3 373
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 45,055评论 2 355

推荐阅读更多精彩内容