28. Find the Index of the First Occurrence in a String

public class Solution {
    public int StrStr(string haystack, string needle) {
        int i = 0,
            j = 0;
        int[] lps = BuildLPS(needle);
        
        while (i < haystack.Length && j < needle.Length)
            if (haystack[i] == needle[j])
            {
                i++;
                j++;
            }
            else
            {
                if (j > 0)
                    j = lps[j - 1];
                else
                    i++;
            }
        
        return j == needle.Length ? i - j : -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 + 1;
                
                i++;
                j++;
            }
            else
            {
                if (i > 0)
                    i = lps[i - 1];
                else
                    j++;
            }
        
        return lps;
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int StrStr(string haystack, string needle) {
        int i = 0,
            j = 0;
        vector<int>& lps = BuildLPS(needle);
        
        while (i < haystack.size() && j < needle.size())
            if (haystack[i] == needle[j])
            {
                i++;
                j++;
            }
            else
            {
                if (j > 0)
                    j = lps[j - 1];
                else
                    i++;
            }
        
        return j == needle.size() ? i - j : -1;
    }
    
    private vector<int>& BuildLPS(string needle)
    {
        vector<int>& lps = new int[needle.size()];
        int i = 0;
        
        for (int j = 1; j < needle.size();)
            if (needle[i] == needle[j])
            {
                lps[j] = i + 1;
                
                i++;
                j++;
            }
            else
            {
                if (i > 0)
                    i = lps[i - 1];
                else
                    j++;
            }
        
        return lps;
    }
}

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;
    }
}

function strStr(haystack, needle) {
  if (needle === "") return 0;

  for (let i = 0; i <= haystack.length - needle.length; i++) {
    let haySlice = haystack.slice(i, i + needle.length);
    if (haySlice === needle) {
      return i;
    }
  }

  return -1;
}

class Solution(object): 
    def strStr(self, haystack, needle): 
        # makes sure we don't iterate through a substring that is shorter than needle 
        for i in range(len(haystack) - len(needle) + 1): 
            # check if any substring of haystack with the same length as needle is equal to needle 
            if haystack[i : i+len(needle)] == needle: 
                # if yes, we return the first index of that substring 
                return i 
        # if we exit the loop, return -1         
        return -1

func strStr(haystack string, needle string) int {
    n := len(needle)
    if n == 0 {
        return 0
    }
    for i := 0; i <= len(haystack)-n; i++ {
        if haystack[i:i+n] == needle {
            return i
        }
    }
    return -1
}

Explanation

Данный код представляет собой класс `Solution`, в котором содержится метод `StrStr`, реализующий алгоритм поиска подстроки `needle` в строке `haystack` с использованием метода Knuth-Morris-Pratt (KMP). В методе используются вспомогательные методы `BuildLPS` для построения массива длин префиксов и суффиксов (LPS) для строки `needle`. Вот пояснение к данному методу:

1. Метод `StrStr` принимает две строки `haystack` и `needle` и возвращает индекс первого вхождения подстроки `needle` в строку `haystack`. Если подстрока не найдена, метод возвращает -1.

2. В методе создаются переменные `i` и `j`, которые используются для перемещения по строкам `haystack` и `needle` соответственно.

3. Сначала вызывается метод `BuildLPS` для строительства массива `lps` (LPS) для подстроки `needle`.

4. Затем запускается цикл `while`, который продолжается, пока не достигнут конец строки `haystack` или строки `needle`.

5. Внутри цикла проверяется, если текущие символы `haystack[i]` и `needle[j]` совпадают, то инкрементируются оба индекса для продолжения сравнения.

6. В случае несовпадения символов, в зависимости от значения `j` происходит смещение индекса `j` по массиву `lps`, либо увеличивается индекс `i`.

7. По завершению цикла проверяется, была ли найдена подстрока (`j == needle.Length`). Если подстрока найдена, то возвращается индекс начала найденной подстроки, иначе возвращается -1.

Метод `BuildLPS` строит массив LPS, который используется для эффективного сравнения строк при поиске подстроки. Он также использует алгоритм KMP для построения этого массива. В итоге код позволяет эффективно находить подстроки в строке, используя метод KMP.