小yi的blog

从前很忙

28. 实现 strStr()--简单难度？

发表于 更新于 分类于 阅读次数： Valine：
本文字数： 1.4k 阅读时长 ≈ 1 分钟

题目描述

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

Sunday算法

这是一道字符串匹配的常见题型，常规算法两个for循环解决；但是，除了KMP这种不太容易手撕的算法外，Sunday算法可以说是一种非常容易理解和实现的算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    //sunday算法Java实现
    int MAXSIZE = 256;
    int moveLength[] = new int[MAXSIZE];
    public int strStr(String haystack, String needle) {
        getMoveLength(needle);
        int len1 = haystack.length();
        int len2 = needle.length();
        int i = 0;
        if(needle==null||"".equals(needle))
            return 0;
        while(i < len1) {
            int j = 0;
            for(  ;j < len2 && i + j < len1 && haystack.charAt(i + j) == needle.charAt(j); ++ j);

            if(j >= len2) return i;
            if(i + len2 >= len1)
                return -1;
            i+=moveLength[haystack.charAt(i + len2)];
        }
        return -1;
    }
    void getMoveLength(String needle) {
        //关键！，根据256种字符类型而不是needle串中的字符确定移动步数
        int len = needle.length();   
        for(int i=0; i < MAXSIZE; ++ i)
        //初始化
            moveLength[i] = len + 1;
            
        for(int i = 0; i<len ; ++ i){
            moveLength[needle.charAt(i)] = len - i;
        }
    }
}

算法思想

从前往后匹配，每次匹配过程的末尾的下一位去检查该字符是否存在于模式串中：

  1. 若存在于模式串中，则返回i的移动步数move=模式串长度- 所在字符的位置最后一个出现位置

  2. 若不存在，则move=模式串长度+1

算法本身其实很容易理解，主要在实现查询办法时需要注意，每次去模式串中查找某个字符效率会比较低下，且算法设计很冗余，较好的办法可以如上述代码，设计一个大小为256的数组，用于存储每个字符的移动步数，这样检索时不会有重复检索问题，效率会高不少。

缺点

缺点很明显，主要有两点：

  1. 即已经匹配的部分字符串完全没有利用，被浪费。

  2. Sunday算法的效率受到匹配串和模式串的影响。

    主串：baaaabaaaabaaaabaaaa

    模式串：aaaaa

    这个模式串使得move[a]的值为1，即每次匹配失败时，只让模式串向后移动一位再进行匹配。这样就让Sunday算法的时间复杂度飙升到了O(m*n)，即字符串匹配常规情况。

此外，不得不吐槽的是，Leetcode官方认为这道题时简单题，给出的数据完全对Sunday算法不利，反而常规算法这道题效率更高。