Leetcode每日一题(6)

· ☕ 3 分钟 · 👻 Victor
🏷️
  • #leetcode
  • #KMP
  • 28. 实现 strStr()

    实现 strStr() 函数。

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

    示例 1:

    输入: haystack = "hello", needle = "ll"
    输出: 2
    

    示例 2:

    输入: haystack = "aaaaa", needle = "bba"
    输出: -1
    

    说明:

    needle 是空字符串时,我们应当返回什么值呢?这是一个在面试中很好的问题。

    对于本题而言,当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。

    分析

    使用KMP算法。

    KMP算法

    KMP 是一种模式匹配算法,要解决的问题可以形式化为:给定模式串 T 与目标串 S,我们要在目标串 S 中寻找 T 的所有出现。

    使用KMP算法最关键的一步是构建next数组。next[i]储存的是string中前i+1位字符串前缀和后缀的最长长度。如abadefg,next[2]存的是aba这个字符串前缀和后缀的最长长度。但是这里为了和代码相对应,将next数组的大小设置为字符串的长度加1。

    假如我们现在求字符串"abababac"的next数组:

    在下标为0的时候设置next[0] = -1;并且i = 0,j = -1

    index 0 1 2 3 4 5 6 7 8
    str NULL a b a b a b a c
    next -1

    一个字符的字符串的最长相同前缀和后缀的长度为0,此时i = 1,j = 0

    index 0 1 2 3 4 5 6 7 8
    str NULL a b a b a b a c
    next -1 0

    接下来str[j] != str[i],j的值又变为next[j] = next[0] = -1;然后继续执行得到next[++i] = ++j,即next[2] = 0,此时i = 2,j = 0;

    index 0 1 2 3 4 5 6 7 8
    str NULL a b a b a b a c
    next -1 0 0

    接下来str[j] == str[i] ,next[++i] = ++j,即next[30] = 1,此时i = 3,j = 1

    index 0 1 2 3 4 5 6 7 8
    str NULL a b a b a b a c
    next -1 0 0 1

    接下来str[i] == str[j],则next[++i] = ++j,即next[4] = 2,此时i = 4,j = 2

    index 0 1 2 3 4 5 6 7 8
    str NULL a b a b a b a c
    next -1 0 0 1 2

    接下来str[i] == str[j],则next[++i] = ++j,即next[5] = 3,此时i = 5,j = 3

    index 0 1 2 3 4 5 6 7 8
    str NULL a b a b a b a c
    next -1 0 0 1 2 3

    接下来str[i] == str[j],则next[++i] = ++j,即next[6] = 4,此时i = 6,j = 4

    index 0 1 2 3 4 5 6 7 8
    str NULL a b a b a b a c
    next -1 0 0 1 2 3 4

    接下来str[i] == str[j],则next[++i] = ++j,即next[7] = 5,此时i = 7,j = 5

    index 0 1 2 3 4 5 6 7 8
    str NULL a b a b a b a c
    next -1 0 0 1 2 3 4 5

    接下来str[i] != str[j],j = next[j] = next[5] = 3;i = 7;此时str[3] != str[7],j = next[j] = next[3] = 1;此时str[1] != str[7],j = next[j] = next[1] = 0;此时str[0] != str[7],j = next[j] = next[0] = -1;接下来next[++i] = next[8] = ++j = 0

    index 0 1 2 3 4 5 6 7 8
    str NULL a b a b a b a c
    next -1 0 0 1 2 3 4 5 0

    匹配字符串的思路与构建next数组的思路类似。

    代码

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    
    class Solution {
    public:
        int strStr(string haystack, string needle) {
            if(needle == "") return 0;
            int n = haystack.length();
            // 构建next数组
            int m = needle.length();
            vector<int> next(m + 1,0);
            for(int i = 0,j = next[0] = -1;i < m;next[++i] = ++j)
                while(~j && needle[j] != needle[i]) j = next[j];
            
            // 搜索
            for(int i = 0,j = 0;i < n;++i)
            {
                while(j > 0 && haystack[i] != needle[j]) j = next[j];
                if(haystack[i] == needle[j]) ++j;
                if(j == m) return (i - m + 1);
            }
            return -1;
        }
    };
    

    参考链接:

    1. 【算法ABC】KMP 算法
    2. 动态规划之KMP字符匹配算法
    3. 从头到尾彻底理解KMP
    分享

    redisread
    作者
    Victor
    Full Stack