28. Найти индекс подстроки (Find the Index of the First Occurrence in a String)

Задание.

Даны две строки needle (иголка) и haystack (стог сена).

Нужно вернуть индекс первого появления строки needle в строке haystack или -1, если строки needle нет в строке haystack.

Пример 1.

Входные данные: haystack = “sadbutsad”, needle = “sad”

Результат: 0

Пояснение: sad встречается при индексах 0 и 6. Первое вхождение имеет индекс 0, поэтому нужно вернуть 0.

Пример 2.

Входные данные: haystack = “leetcode”, needle = “leeto”

Результат: -1

Пояснение: leeto не встречается в leetcode, поэтому возвращается -1.

Решение.

class Solution {
public:
    int strStr(string haystack, string needle) {
        int n = haystack.length(), l = needle.length(), i, j;
        for(i = 0; i < n-l+1; i++) {
            if(haystack[i] == needle[0]) {
                for(j = 1; j < l; j++) {
                    if(haystack[i+j] != needle[j]) {
                        // нет совпадения, выходим
                        break;
                    }
                }
                if(j == l) {
                    // нашлось полное совпадение
                    return i;
                }
            }
        }
        return -1;
    }
};

Пояснение.

Продвигаемся по строке haystack до тех пор, пока может встретиться строка needle (не до самого конца haystack, а до разницы размеров haystack и needle).

Как только в строке haystack замечаем первый символ из needle, запускаем проверку символов needle в haystack.

Если все символы в строках совпадут, возвращается индекс первого вхождения.

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