"""Knuth-Morris-Pratt substring search.

Provides:
  - build_pi(pattern): prefix (failure) function, O(m)
  - search(text, pattern): all start indices, O(n+m)
  - search_count(text, pattern): number of (possibly overlapping) occurrences

Correctness notes:
  * Empty pattern matches at every position (0..len(text)) per Python str.find semantics? We return [] for empty pattern to avoid O(n) noise; callers wanting positions can handle separately. Actually we return list(range(len(text)+1)) to match str.find('') behaviour? Tests pin: empty pattern -> [] (documented).
  * Overlapping occurrences are reported.
"""

from typing import List


def build_pi(pattern: str) -> List[int]:
    m = len(pattern)
    pi = [0] * m
    k = 0
    for i in range(1, m):
        while k > 0 and pattern[i] != pattern[k]:
            k = pi[k - 1]
        if pattern[i] == pattern[k]:
            k += 1
        pi[i] = k
    return pi


def search(text: str, pattern: str) -> List[int]:
    if not pattern:
        return []
    n, m = len(text), len(pattern)
    if m > n:
        return []
    pi = build_pi(pattern)
    res: List[int] = []
    k = 0
    for i in range(n):
        while k > 0 and text[i] != pattern[k]:
            k = pi[k - 1]
        if text[i] == pattern[k]:
            k += 1
        if k == m:
            res.append(i - m + 1)
            k = pi[k - 1]
    return res


def search_count(text: str, pattern: str) -> int:
    return len(search(text, pattern))