02 算法体系班 - 21 KMP算法 - 《java笔记》

什么是KMP
- KMP算法实现
KMP应用
- 题目1：判断数的子树结构是否与另一个二叉树完全一样
- 题目2：判断是否为旋转字符串

什么是KMP

假设字符串str长度为N，字符串match长度为M，M <= N想确定str中是否有某个子串是等于match的。时间复杂度O(N)的匹配算法
KMP算法的核心 理解next数组

KMP算法实现

**
 * KMP算法实现
 *
 * @author :Administrator
 * @date :2022/5/12 0012
 */
public class KMP {
    public static int getIndexOf(String s, String m) {
        if (s.length() < m.length()) {
            return -1;
        }
        char[] sChars = s.toCharArray();
        char[] mChars = m.toCharArray();
        int sIndex = 0;
        int mIndex = 0;
        // next[i] i位置之前，0~i-1,前缀与后缀字符串相匹配的最大长度
        int[] next = getNextArray(mChars);
        while (sIndex < sChars.length && mIndex < mChars.length) {
            // 如果sIndex位置与mIndex位置匹配，则都前进
            if (sChars[sIndex] == mChars[mIndex]) {
                sIndex++;
                mIndex++;
            }
            //  如果mIndex=0,还无法配置，sIndex前进，m字符串从0开始匹配
            else if (next[mIndex] == -1) {
                sIndex++;
            } else {
                // 否则从next[mIndex] 位子开始匹配
                mIndex = next[mIndex];
            }
        }
        return mIndex == mChars.length ? sIndex - mIndex : -1;
    }
    private static int[] getNextArray(char[] mChars) {
        if (mChars.length == 1) {
            return new int[]{-1};
        }
        int[] next = new int[mChars.length];
        next[0] = -1;
        next[1] = 0;
        int pos = 2;
        int cn = 0;
        while (pos < next.length) {
            // next[i] -> cn = next[i-1]  如果mChars[i-1] == mChars[cn] 则 next[i] = cn+1;
            if (mChars[pos - 1] == mChars[cn]) {
                next[pos++] = ++cn;
            } else if (cn > 0) {
                // 如果mChars[i-1] != mChars[cn]  cn = next[cn]
                cn = next[cn];
            } else {
                // 如果cn==0 表示来到mChar[0]!=mChars[pos-1] 则没有前缀和后缀相等的字符串
                next[pos++] = 0;
            }
        }
        return next;
    }
}

KMP应用

题目1：判断数的子树结构是否与另一个二叉树完全一样

给定两棵二叉树的头节点head1和head2，想知道head1中是否有某个子树的结构和head2完全一样

static class TreeNode {
    private int value;
    private TreeNode left;
    private TreeNode right;
    public TreeNode(int value) {
        this.value = value;
    }
}
public static boolean containsTree1(TreeNode big, TreeNode small) {
    if (small == null) {
        return true;
    }
    if (big == null) {
        return false;
    }
    if (isSameValueStructure(big, small)) {
        return true;
    }
    return containsTree1(big.left, small) || containsTree1(big.right, small);
}
public static boolean isSameValueStructure(TreeNode head1, TreeNode head2) {
    if (head1 == null && head2 != null) {
        return false;
    }
    if (head1 != null && head2 == null) {
        return false;
    }
    if (head1 == null && head2 == null) {
        return true;
    }
    if (head1.value != head2.value) {
        return false;
    }
    return isSameValueStructure(head1.left, head2.left)
        && isSameValueStructure(head1.right, head2.right);
}

static class TreeNode {
    private int value;
    private TreeNode left;
    private TreeNode right;
    public TreeNode(int value) {
        this.value = value;
    }
}
public static boolean containsSameSubTree(TreeNode head1, TreeNode head2) {
    if (head2 == null) {
        return true;
    }
    if (head1 == null) {
        return false;
    }
    ArrayList<String> list1 = new ArrayList<>();
    ArrayList<String> list2 = new ArrayList<>();
    list1 = preProcess(head1, list1);
    list2 = preProcess(head2, list2);
    return getIndex(list1, list2) != -1;
}
private static ArrayList<String> preProcess(TreeNode head, ArrayList<String> list) {
    if (head == null) {
        list.add(null);
        return list;
    }
    list.add(String.valueOf(head.value));
    preProcess(head.left, list);
    preProcess(head.right, list);
    return list;
}
private static int getIndex(ArrayList<String> list1, ArrayList<String> list2) {
    if (list1 == null || list2 == null || list1.size() < 1 || list1.size() < list2.size()) {
        return -1;
    }
    int n = list1.size(), m = list2.size();
    int[] next = getNextArray(list2);
    int i1 = 0;
    int i2 = 0;
    while (i1 < n && i2 < m) {
        if (Objects.equals(list1.get(i1), list2.get(i2))) {
            i1++;
            i2++;
        } else if (next[i2] == -1) {
            i1++;
        } else {
            i2 = next[i2];
        }
    }
    return i2 == m ? i1 - i2 : -1;
}
private static int[] getNextArray(ArrayList<String> list) {
    if (list == null || list.size() == 0) {
        return null;
    }
    int n = list.size();
    if (n == 1) {
        return new int[]{-1};
    }
    int[] next = new int[n];
    next[0] = -1;
    next[1] = 0;
    int pos = 2;
    int cn = 0;
    while (pos < n) {
        if (Objects.equals(list.get(pos - 1), list.get(cn))) {
            next[pos++] = ++cn;
        } else if (cn > 0) {
            cn = next[cn];
        } else {
            next[pos++] = 0;
        }
    }
    return next;
}

题目2：判断是否为旋转字符串

判断str1和str2是否是旋转字符串。例：str1 : abcdefg ——》旋转字符串：(1) 以0号字符旋转：abcdefg (2) 以1号字符旋转 bcdefga (3)以2号字符旋转 cdefgab ……

/*
     * 判断str1和str2是否是旋转字符串
     * 例：
     * str1 :  abcdefg ——》旋转字符串：(1) 以0号字符旋转：abcdefg (2) 以1号字符旋转 bcdefga (3)以2号 字符旋转 cdefgab ……
     *         0123456
     * */

public static boolean isRotation(String str1, String str2) {
    if (str1 == null || str2 == null || str1.length() != str2.length()) {
        return false;
    }

    String str = str1.concat(str1);

    return getIndexSubString(str, str2) != -1;
}

private static int getIndexSubString(String s1, String s2) {

    if (s1 == null || s2 == null || s1.length() < 1 || s1.length() < s2.length()) {
        return -1;
    }


    int i1 = 0;
    int i2 = 0;
    char[] chars1 = s1.toCharArray();
    char[] chars2 = s2.toCharArray();

    int[] next = getNextArray(chars2);

    while (i1 < chars1.length && i2 < chars2.length) {
        if (chars1[i1] == chars1[i2]) {
            i1++;
            i2++;
        } else if (next[i2] == -1) {
            i1++;
        } else {
            i2 = next[i2];
        }
    }

    return i2 == chars2.length ? i1 - i2 : -1;
}

private static int[] getNextArray(char[] chars) {
    if (chars.length == 1) {
        return new int[]{-1};
    }
    int[] next = new int[chars.length];

    next[0] = -1;
    next[1] = 0;
    int i = 2;
    int cn = 0;

    while (i < next.length) {
        if (chars[i - 1] == chars[cn]) {
            next[i++] = ++cn;
        } else if (cn > 0) {
            cn = next[cn];
        } else {
            next[i++] = 0;
        }
    }
    return next;
}