Untitled

package fun.proteinpill;

/**
 * @Project JavaLeetcode
 * @Author godot
 * @Create 2023-08-02 14:17
 */
public class FindTheIndexOfTheFirstOccurrenceInAString {
    public static void main(String[] args) {
        System.out.println(strStr("leetcode", "leeto"));
    }

    public static int strStr(String haystack, String needle) {
        int needleLength = needle.length();
        int haystackLength = haystack.length();
        if (needleLength > haystackLength) {
            return -1;
        }
        if (needleLength == haystackLength) {
            return haystack.equals(needle) ? 0 : -1;
        }
        int[] next = new int[needle.length()];
        int prefixLength = 0;
        for (int i = 1; i < needle.length(); i++) {
            char c = needle.charAt(i);
            if (c == needle.charAt(prefixLength)) {
                prefixLength++;
                next[i] = prefixLength;
            } else if (prefixLength == 0) {
                next[i] = 0;
            } else {
                prefixLength = next[prefixLength - 1];
                i--;
            }
        }
        int needlePtr = 0;
        int haystackPtr = 0;
        while (haystackPtr < haystackLength) {
            char c = haystack.charAt(haystackPtr);
            if (c == needle.charAt(needlePtr)) {
                haystackPtr++;
                needlePtr++;
            } else if (needlePtr > 0) {
                needlePtr = next[needlePtr - 1];
            } else {
                haystackPtr++;
            }
            if (needlePtr == needleLength) {
                return haystackPtr - needlePtr;
            }
        }
        return -1;
    }
}