1text = "hello world"
2
3# Returns the index of the first occurrence, or -1 if not found
4idx = text.find("world")   # 6
5idx = text.find("xyz")     # -1
6
7# Optional start and end parameters
8idx = text.find("o", 5)    # 7 (search from index 5)
9idx = text.find("l", 0, 5) # 2 (search in text[0:5])

1# Worst case: many partial matches before failure
2text = "a" * 1_000_000        # "aaaaaa...a" (1M characters)
3pattern = "a" * 999 + "b"     # "aaa...ab" (999 a's + b)
4
5# The algorithm must check 999 characters at each position
6# before discovering the mismatch at position 999
7idx = text.find(pattern)      # -1 (not found), O(n * m) comparisons

11. For short patterns (m <= 5): use a simple loop
22. For longer patterns: use a two-way string matching variant
3   - Boyer-Moore-Horspool bad character table for skipping
4   - Sunday's improvement for the shift after a mismatch
5   - Bloom filter to quickly check if a character appears in the pattern

1# The bloom filter optimization:
2# Before doing a full comparison, CPython checks if the character
3# at the end of the window appears in the pattern using a bitmask.
4# If not, it skips the entire pattern length.
5
6# This makes searches through text with varied characters very fast:
7text = "The quick brown fox jumps over the lazy dog" * 10000
8idx = text.find("xyz")  # Very fast — bloom filter skips most positions

1import timeit
2
3# Average case: random text, short pattern
4text = "abcdefghij" * 100000  # 1M chars
5pattern = "xyz"
6timeit.timeit(lambda: text.find(pattern), number=100)
7# ~0.01s — O(n) behavior, fast skipping
8
9# Near worst case: repeated characters
10text = "a" * 1_000_000
11pattern = "a" * 100 + "b"
12timeit.timeit(lambda: text.find(pattern), number=10)
13# ~0.5s — O(n * m) behavior, slow
14
15# Comparison with 're' module
16import re
17timeit.timeit(lambda: re.search(pattern, text), number=10)
18# Similar or slower — regex adds overhead for simple searches

1# Pattern 1: Repeated characters (classic worst case)
2"a" * n  .find("a" * m + "b")  # O(n * m)
3
4# Pattern 2: Near-matches throughout
5"ababab...ab".find("ababac")   # Many partial matches
6
7# Pattern 3: Very long patterns in periodic text
8"abcabc...abc".find("abc" * 1000 + "d")  # O(n * m)

1# For guaranteed O(n + m): use KMP or Aho-Corasick
2# KMP implementation
3def kmp_search(text, pattern):
4    n, m = len(text), len(pattern)
5
6    # Build failure function
7    fail = [0] * m
8    j = 0
9    for i in range(1, m):
10        while j > 0 and pattern[i] != pattern[j]:
11            j = fail[j - 1]
12        if pattern[i] == pattern[j]:
13            j += 1
14        fail[i] = j
15
16    # Search
17    j = 0
18    for i in range(n):
19        while j > 0 and text[i] != pattern[j]:
20            j = fail[j - 1]
21        if text[i] == pattern[j]:
22            j += 1
23        if j == m:
24            return i - m + 1
25    return -1
26
27# For multiple pattern search: use Aho-Corasick (pyahocorasick package)
28# For regex patterns: use 're' module (uses different algorithms)

1# These have identical performance characteristics
2if "pattern" in text:       # Uses fastsearch internally
3    pass
4
5if text.find("pattern") != -1:  # Same algorithm
6    pass
7
8# str.index() also uses the same algorithm but raises ValueError instead of -1