废话

今天之前，我只知道KMP（看猫片）算法，昨天刚看了28. 实现 strStr()，今天早上刚刚从一个KMP算法的评论里面知道了还有这个Sunday算法，作为一个程序员，我最喜欢周末了。

字符串匹配算法通常包含BF、KMP、BM、Sunday。

• BF是最简单暴力的算法

• KMP是最广为人知的算法

• BM效率高，复杂

• Sunday简单且高效

正文

Sunday算法的最主要特点就是思路简单，不像KMP。

如图，在匹配不上的时候，直接比较“主串”此次匹配结束位置的后一位是否在“模式串”中

• 不在（图中i不在模式串中），则主串中比对的起点（图中的起点是s）向后移动模式串的长度+1（s->6+1=n）;
  
  比较n，又不等，又如上看结束后的后一位（r）：
• 在（r在模式串中），则主串起点向后移动"模式串长度-字符在模式串中最后一次出现的下标"（从n->(6-3)=s）
  
  继续比对，匹配长度等于模式串长度，匹配成功，返回当前起点。

代码

/**
 * 学习sunday算法
 */
fun strStr(haystack: String, needle: String): Int {
    if(needle.isEmpty())
        return 0
    val len1=haystack.length
    val len2=needle.length

    if(len2>len1)
        return -1

    //build the last map
    val map= mutableMapOf<Char,Int>()
    needle.forEachIndexed { index, c ->
        map[c] = index
    }
    var start=0 //current start in haystack
    var compareCount=0
    while(start+len2<=len1){
        compareCount=0
        while(haystack[start+compareCount]==needle[compareCount]){
            compareCount++
            if(compareCount==len2)
                return start
        }

        val checkIndex=start+len2

        val lastIndex =if(checkIndex<len1) map[haystack[checkIndex]] else null
        start += if(lastIndex!=null){
            len2-lastIndex
        }else{
            start+len2+1

        }

    }
    return -1
}

最后

本来今天挺累的，想早点睡觉的，结果写这点代码+这篇文章就花了两个多小时，就为了拿到盘Android的文章分享积分，真不容易呀

参考资料

字符串匹配之Sunday算法
字符串匹配——Sunday算法