Задача: №28. Find the Index of the First Occurrence in a String
Сложность: easy

Учитывая две строки needle и haystack, вернуть индекс первого вхождения needle в haystack, либо -1, если needle не содержится в haystack.

Пример:

Input: haystack = "sadbutsad", needle = "sad" Output: 0

👨‍💻 Алгоритм:

1⃣Проверить граничный случай: если needle пустая — вернуть 0.

2⃣Построить функцию сбоев (prefix function) для строки needle по алгоритму Кнута-Морриса-Пратта (КМП), чтобы ускорить поиск.

3⃣Пройти по строке haystack и при совпадении символов с needle — продвигать указатель. Если несовпадение — использовать функцию сбоев для эффективного сдвига.

😎 Решение:

public class Solution {

    private int[] failureFunction(char[] str) {
        int[] f = new int[str.length + 1];
        for (int i = 2; i < f.length; i++) {
            int j = f[i - 1];
            while (j > 0 && str[j] != str[i - 1]) j = f[j];
            if (j > 0 || str[j] == str[i - 1]) f[i] = j + 1;
        }
        return f;
    }

    public int strStr(String haystack, String needle) {
        if (needle.length() == 0) return 0;
        if (needle.length() <= haystack.length()) {
            int[] f = failureFunction(needle.toCharArray());
            int i = 0, j = 0;
            while (i < haystack.length()) {
                if (haystack.charAt(i) == needle.charAt(j)) {
                    i++; j++;
                    if (j == needle.length()) return i - j;
                } else if (j > 0) {
                    j = f[j];
                } else {
                    i++;
                }
            }
        }
        return -1;
    }
}

Ставь 👍 и забирай 📚 Базу знаний