28. Реализуйте strStr()

алгоритм

Реализуйте функцию strStr().

Имея две строки haystack и игла, найдите первую позицию строки иглы в строке стога сена (индекс начинается с 0). Возвращает -1, если отсутствует.

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

Решение первое

решение грубой силыПерейдите строку стога сена, чтобы сопоставить все подстроки в стоге сена той же длины, что и строка иглы.

def strStr1(haystack, needle):
    """暴力解法"""

    m, n = len(haystack), len(needle)
    for i in range(m - n + 1):  # i 可以等于 m-n, 所以这里需要 +1
        flag = True  # 记录子串是否相等，默认为True
        for j in range(n):
            if haystack[i + j] != needle[j]:  # 如果有一个字符不相等，就说明子串不相等，退出循环
                flag = False
                break
        if flag: return i  # 如果循环结束，flag还是为True，说明子串相等，此时的i就是起始位置
    return -1  # 如果循环结束，还是没有，就说明没有匹配的子串，直接返回 -1
Анализ сложности
  • Временная сложность: m — длина исходной строки, n — длина соответствующей строки. Сложность перечисленияO(m−n)О (м-п), сложность построения и сравнения строк составляетO(n)O(n). Общая сложность составляетO((m−n)*n)O((m−n)∗n).
  • Сложность пространства:O(1)O(1).

Решение второе

Алгоритм КМППо сути, это оптимизация решения брутфорса выше.

смысл:В случае несовпадения строк вы можете записать часть текстового содержимого, которое было сопоставлено ранее, и использовать эту информацию, чтобы не выполнять сопоставление с самого начала.

Пожалуйста, ознакомьтесь с конкретным анализом процесса (для тех, у кого нет опыта KMP, эти объяснения легче понять):

Подробное объяснение алгоритма KMP «Code Casual Recording»

Помочь вам изучить алгоритм KMP досконально! (теория)

Помочь вам изучить алгоритм KMP досконально! (поиск следующего кода массива)

def strStr2(haystack, needle):
    """KMP算法 前缀表（不减一）实现"""

    def getNext(s):
        """求s的next数组，也就是s各个位置对应的前缀表"""
        nex = ['' for _ in range(len(s))]  # 初始化next数组
        j = 0  # j 指向前缀末尾
        nex[0] = 0  # 初始化第一位的值，因为字符串的第一位的前后缀的长度都为0
        for i in range(1, len(s)):  # i 指向后缀末尾，从1开始，前后缀末尾才能比较
            while j > 0 and s[i] != s[j]:  # j 要保证大于0，因为下面有取j-1作为数组下标的操作
                # 当前后缀末尾不相同时，意味着前后缀的相同长度不能再 +1
                # 并且等于前一位的前后缀最大相同长度，即前一位的回退位置
                j = nex[j - 1]
            if s[i] == s[j]:
                j += 1  # 当前后缀末尾相同时，意味着前后缀的相同长度再 +1
            nex[i] = j  # 对数组进行赋值，j就是s[0:i]字符串的前后缀的最长相同长度
        return nex

    # 特殊情况判断
    if not needle: return 0

    m, n = len(haystack), len(needle)
    nex = getNext(needle)  # 获取needle的前缀表
    j = 0  # 表示指向needle的下标，默认从0开始
    for i in range(m):  # i表示haystack的下标 就从0开始，遍历haystack字符串
        while j > 0 and haystack[i] != needle[j]:
            # 当出现不匹配时，j就等于前一个位置的前后缀的最长相同长度，即前缀表中的值
            # 即j就跳到最长前缀的下一位，重新开始匹配
            j = nex[j - 1]
        if haystack[i] == needle[j]:
            # 当匹配时，继续比较下一位，j和i同时向右移动一位，i的增加在for循环里面
            j += 1
        if j == n:
            # 当j等于n时，表示文本串haystack里已经出现了模式串needle，返回needle的起始位置
            return i - n + 1
    return -1  # 上面的遍历结束，还没有出现模式串needle，说明不存在，返回-1
Анализ сложности
  • временная сложность:O(n+m)O(n+m), где n — длина стога сена, а m — длина иголки. Нам нужно перебрать обе строки не более одного раза.
  • Сложность пространства:O(m)O(m), где m — длина струнной иглы. Нам просто нужно сохранить функцию префикса для струнной иглы.

Официальный ответ Ликоу

Категории