Implement strStr()

Problem Id: 28 Difficulty: Easy Tag: Two Pointers Tag: String


Intuition

Just directly use [KMP](https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm) to solve this problem.

This problem is at least a hard problem without using built-in functions. Don't know what's wrong with leetcode's diffculty system.

Solution


class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if needle == '':
            return 0

        pattern = self._build(needle)
        return self._search(haystack, needle, pattern)

    def _build(self, word):
        pattern = [-1] * len(word)
        cnd = 0
        for pos in range(1, len(word)):
            pattern[pos] = cnd
            while cnd >= 0 and word[cnd] != word[pos]:
                cnd = pattern[cnd]
            cnd += 1
        return pattern

    def _search(self, s, w, t):
        cnd = 0
        for i in range(len(s)):
            while cnd >= 0 and s[i] != w[cnd]:
                cnd = t[cnd]
            cnd += 1

            if cnd == len(w):
                return i - len(w) + 1
        return -1