Проверка на подстроку

Решение: Алгоритм поиска подстроки без встроенных методов

Подход

Для поиска подстроки в строке без встроенных методов используются два основных алгоритма: наивный и эффективный (KMP). Здесь представлены обе реализации с объяснением.

1. Наивный алгоритм O(n*m)

Проверяем каждую позицию в основной строке и сравниваем посимвольно.

def strStr_naive(haystack: str, needle: str) -> int:
    """
    Наивный поиск подстроки.
    Time: O(n*m) где n=len(haystack), m=len(needle)
    Space: O(1)
    """
    if not needle:
        return 0
    
    if len(needle) > len(haystack):
        return -1
    
    for i in range(len(haystack) - len(needle) + 1):
        # Проверяем совпадение на позиции i
        match = True
        for j in range(len(needle)):
            if haystack[i + j] != needle[j]:
                match = False
                break
        
        if match:
            return i
    
    return -1

2. KMP алгоритм O(n+m)

Добавляет препроцессинг для построения таблицы смещений (failure function).

def strStr_kmp(haystack: str, needle: str) -> int:
    """
    KMP (Knuth-Morris-Pratt) алгоритм.
    Time: O(n+m)
    Space: O(m)
    """
    if not needle:
        return 0
    
    if len(needle) > len(haystack):
        return -1
    
    # Построение таблицы смещений
    lps = build_lps(needle)
    
    i = 0  # индекс в haystack
    j = 0  # индекс в needle
    
    while i < len(haystack):
        if haystack[i] == needle[j]:
            i += 1
            j += 1
        
        if j == len(needle):
            return i - j  # Найдено!
        
        elif i < len(haystack) and haystack[i] != needle[j]:
            if j != 0:
                j = lps[j - 1]  # Используем таблицу смещений
            else:
                i += 1
    
    return -1

def build_lps(pattern: str) -> list:
    """
    LPS = Longest Proper Prefix which is also Suffix
    Строит таблицу смещений для KMP.
    """
    n = len(pattern)
    lps = [0] * n
    length = 0  # длина совпадающего префикса-суффикса
    i = 1
    
    while i < n:
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1
    
    return lps

3. Примеры использования

# Пример 1: Базовый случай
result = strStr_kmp("hello", "ll")
print(result)  # 2

# Пример 2: Не найдено
result = strStr_kmp("hello", "world")
print(result)  # -1

# Пример 3: Подстрока в начале
result = strStr_kmp("hello", "he")
print(result)  # 0

# Пример 4: Подстрока в конце
result = strStr_kmp("hello", "lo")
print(result)  # 3

# Пример 5: Пустая подстрока
result = strStr_kmp("hello", "")
print(result)  # 0 (по соглашению)

# Пример 6: Повторяющиеся паттерны
result = strStr_kmp("ababdababa", "abab")
print(result)  # 0

result = strStr_kmp("ababdababa", "bab")
print(result)  # 1

4. Трассировка KMP

Для haystack = "hello", needle = "ll":

Шаг 1: Построение LPS таблицы для "ll"
  pattern = "ll"
  lps = [0, 1]
  (второй 'l' имеет смещение 1)

Шаг 2: Поиск
  i=0, j=0: h != l, j=0, i=1
  i=1, j=0: e != l, j=0, i=2
  i=2, j=0: l == l, i=3, j=1
  i=3, j=1: l == l, i=4, j=2
  j==2 (длина needle) → Найдено на позиции 4-2=2

5. Сравнение алгоритмов

6. Реализация на JavaScript

function strStr(haystack, needle) {
    if (!needle) return 0;
    if (needle.length > haystack.length) return -1;
    
    for (let i = 0; i <= haystack.length - needle.length; i++) {
        let match = true;
        for (let j = 0; j < needle.length; j++) {
            if (haystack[i + j] !== needle[j]) {
                match = false;
                break;
            }
        }
        if (match) return i;
    }
    return -1;
}

// Примеры
console.log(strStr("hello", "ll"));     // 2
console.log(strStr("hello", "world")); // -1
console.log(strStr("hello", ""));      // 0

7. Тестирование

def test_strStr():
    test_cases = [
        ("hello", "ll", 2),
        ("hello", "world", -1),
        ("hello", "", 0),
        ("", "a", -1),
        ("", "", 0),
        ("a", "a", 0),
        ("aab", "aab", 0),
        ("aab", "ab", 1),
        ("mississippi", "issip", 4),
        ("aaaa", "aa", 0),  # первое совпадение
    ]
    
    for haystack, needle, expected in test_cases:
        result = strStr_kmp(haystack, needle)
        assert result == expected, f"Failed: {haystack}, {needle} → {result} (expected {expected})"
    
    print("All tests passed!")

test_strStr()

8. Ключевые моменты

1. Edge cases:

   • Пустая подстрока возвращает 0
   • Подстрока больше строки возвращает -1
   • Обе строки пусты возвращают 0

2. Оптимизация:

   • Наивный алгоритм быстрее для очень коротких строк
   • KMP лучше для долгих поисков с повторениями

3. Практическое применение:

   • Pattern matching в текстовых редакторах
   • Поиск ДНК последовательностей в биоинформатике
   • Обнаружение плагиата
   • Поиск вредоноса в сетевом трафике

Это классическая задача на собеседованиях для проверки понимания алгоритмов и оптимизации.