Задача: 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⃣Использовать два указателя i и j для прохода по haystack и needle.

2⃣Применить алгоритм KMP с использованием массива LPS (longest prefix suffix) для оптимального поиска.

3⃣Вернуть индекс первого вхождения needle или -1, если needle не найден.

😎 Решение:

public class Solution {
    public int StrStr(string haystack, string needle) {
        int i = 0, j = 0;
        int[] lps = BuildLPS(needle);
        
        while (i < haystack.Length) {
            if (haystack[i] == needle[j]) {
                i++;
                j++;
                if (j == needle.Length) return i - j;
            } else {
                if (j > 0) j = lps[j - 1];
                else i++;
            }
        }
        
        return -1;
    }
    
    private int[] BuildLPS(string needle) {
        int[] lps = new int[needle.Length];
        int i = 0;

        for (int j = 1; j < needle.Length;) {
            if (needle[i] == needle[j]) {
                lps[j++] = ++i;
            } else {
                if (i > 0) i = lps[i - 1];
                else j++;
            }
        }

        return lps;
    }
}

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