package com.zmz.algorithm.string;

import java.util.Arrays;

/**
 * @author 张明泽
 * Create by 2022/5/26 15:26
 * 实现strStr()
 * KMP算法
 * LeetCode-28
 */
public class StrStr {
    public static void main(String[] args) {
        String haystack = "hello";
        String needle = "ll";
        /**
         * 当发生冲突时,找到冲突的前一个字符与其相等的前缀的后面继续开始匹配
         */
        String test1 = "aabaabaaf";
        String test2 = "aabaaf";
        int result = str(test1,test2);
        int res = str2(haystack,needle);
        System.out.println(result);
        System.out.println(res);
    }

    /**
     * KMP算法
     * 为了解决: 当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。
     * next数组就是一个前缀表
     * 前缀表作用: 用来回退的，它记录了模式串与主串不匹配的时候，模式串应该从哪里开始重新匹配。
     * 是记录下标i之前（包括i）的字符串中，有多大长度的(最长)相同前缀后缀。
     */
    public static int str(String str,String str2) {
        int[] next = new int[str2.length()];
        getNext(next,str2);
        int left = 0;
        for (int right = 0; right < str.length(); right++) {
            while (left > 0 && str.charAt(right) != str2.charAt(left)) {
                left = next[left - 1];
            }
            if (str.charAt(right) == str2.charAt(left)) {
                left++;
            }
            if (left == str2.length()) {
                return right - str2.length() + 1;
            }
        }
        return -1;
    }
    public static void getNext(int[] next, String str) {
        int left = 0;
        next[0] = 0;
        for (int right = 1; right < str.length(); right++) {
            while (left > 0 && str.charAt(left) != str.charAt(right)) {
                left = next[left - 1];
            }
            if (str.charAt(left) == str.charAt(right)) {
                left++;
            }
            next[right] = left;
        }
        System.out.println(Arrays.toString(next));
    }
    /**
     * 简单解法
     */
    public static int str2(String str1,String str2) {
        return str1.indexOf(str2);
    }
}