Понимание решения KMP - Brute Force

Question

Привет. Я пытаюсь понять решение KMP грубой силой.Я выбрал решение в Leetcode.

public static int strStr(String haystack, String needle) {
    if (needle == null || needle.length() < 1) {
        return 0;
    }

    for (int i = 0; i < haystack.length() - needle.length() + 1; i++) {
        if (isValid(haystack, needle, i)) {
            return i;
        }
    }
    return -1;
}

public static boolean isValid(String haystack, String needle, int index) {
    for (int i = 0; i < needle.length(); i++) {
        if (haystack.charAt(index + i) != needle.charAt(i)) {
            return false;
        }
    }
    return true;
}

Здесь мы делаем haystack.length() - needle.length() + 1.Я не могу понять, почему в цикле for мы вычитаем стог сена и длину иглы, а затем добавляем 1 к нему.Может кто-нибудь, пожалуйста, помогите мне понять, почему.Спасибо.

Answer 1

Первый символ needle в haystack не может следовать за позицией haystack.length - needle.length - 1, потому что будет недостаточно символов для сопоставления.Функция isValid будет даже выбрасывать индекс массива за пределы, потому что haystack.charAt(index + i) не будет определен для всех 0 <= i < needle.length.