左神算法笔记——KMP衍生题

题目一

给定一个字符串str，向字符串尾部添加字符，使得添加结束后的字符串包含两个原始字符串str。
问：满足结束条件的最小添加步数，一次只能添加一个元素

分析

这题可以用KMP算法中求解字符串m的preNextArr数组的方式解决。

• 如： aba字符串，3位置的最长公共前后缀的长度为1，所以只需要构成字符串ababa,也就时目前已经存在了1个已有的字符a,只要加上从开始位置的1一直到字符串结束的字符就可以了。
• 如：abcabc字符串，最后一位的最长公共前后追的长度为3，如果只需要在后面加上 6 - 3 = 3位即可，构成abcabcabc 。

代码

    // 获取最少的操作步骤————京东面试题
    public static int getMinStep(String s) {
        // 首先操作的字符串不可以为null
        if(s == null || "".equals(s)) {
            throw new RuntimeException("输入参数有误！");
        }
        int len = s.length();
        // 边界条件判断
        if(len == 1) return 1;
        if(len == 2) return s.charAt(0) == s.charAt(1) ? 1 : 2;
        //将s字符串转化为字符数组进行KMP思想求解
        char[] chars = s.toCharArray();
        return len - getPreNextStep(chars);
    }

    public static int getPreNextStep(char[] chars){
        int[] next = new int[chars.length + 1];
        next[0] = -1;
        next[1] = 0;
        int pos = 2;
        int pre = 0;
        while(pos < next.length){
            if(chars[pos - 1] == chars[pre]){
                next[pos++] = ++pre;
            }else if(pre > 0){
                // 还可以继续跳
                pre = next[pre];
            }else{
                next[pos++] = 0;
            }
        }
        return next[next.length - 1];
    }

    public static void main(String[] args) {
        String s = "abcabc";
        System.out.println(getMinStep(s));
    }

题目二

给定两个头节点t1和t2,请你判断两个树是否为包含关系，即其中一个树是另一个树的子树。

思路

• 首先将两个树分别按照前序遍历的顺序进行序列化，
• 之后就是标准的KMP求解问题，检查t1序列化之后的字符串s1中是否包含t2序列化之后的字符串s2,如果有，则返回true，否则返回false。

代码

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }

    public static boolean isSubtree(Node t1, Node t2) {
        String t1Str = serialByPre(t1);
        String t2Str = serialByPre(t2);
        return getIndexOf(t1Str, t2Str) != -1;
    }

    public static String serialByPre(Node head) {
        if (head == null) {
            return "#!";
        }
        String res = head.value + "!";
        res += serialByPre(head.left);
        res += serialByPre(head.right);
        return res;
    }

    // KMP
    public static int getIndexOf(String s, String m) {
        if (s == null || m == null || m.length() < 1 || s.length() < m.length()) {
            return -1;
        }
        char[] ss = s.toCharArray();
        char[] ms = m.toCharArray();
        int[] nextArr = getNextArray(ms);
        int index = 0;
        int mi = 0;
        while (index < ss.length && mi < ms.length) {
            if (ss[index] == ms[mi]) {
                index++;
                mi++;
            } else if (nextArr[mi] == -1) {
                index++;
            } else {
                mi = nextArr[mi];
            }
        }
        return mi == ms.length ? index - mi : -1;
    }

    public static int[] getNextArray(char[] ms) {
        if (ms.length == 1) {
            return new int[] { -1 };
        }
        int[] nextArr = new int[ms.length];
        nextArr[0] = -1;
        nextArr[1] = 0;
        int pos = 2;
        int cn = 0;
        while (pos < nextArr.length) {
            if (ms[pos - 1] == ms[cn]) {
                nextArr[pos++] = ++cn;
            } else if (cn > 0) {
                cn = nextArr[cn];
            } else {
                nextArr[pos++] = 0;
            }
        }
        return nextArr;
    }

    public static void main(String[] args) {
        Node t1 = new Node(1);
        t1.left = new Node(2);
        t1.right = new Node(3);
        t1.left.left = new Node(4);
        t1.left.right = new Node(5);
        t1.right.left = new Node(6);
        t1.right.right = new Node(7);
        t1.left.left.right = new Node(8);
        t1.left.right.left = new Node(9);

        Node t2 = new Node(2);
        t2.left = new Node(4);
        t2.left.right = new Node(8);
        t2.right = new Node(5);
        t2.right.left = new Node(9);

        System.out.println(isSubtree(t1, t2));
    }