面试题:手动实现字符串替换(KMP算法)

代码共包含两个替换版本

/**
 * 手动实现字符串交换
 * 当时的想法是,将匹配到的位置返回,迭代的将匹配到的字符位置删除,之后插入被替换的值
 */
public class TestMatch {
    public static void main(String[] args) {
//        List<Integer> matchIndex = matchVersion1("abacabcacbab", "ab");
        List<Integer> matchIndex = matchVersion2("abacabcacbab", "ab");
        matchIndex.forEach(System.out::println);
        System.out.println(replace("abacabcacbab", "ab", "abc"));
        System.out.println(replaceTwo("abacabcacbab", "ab", "abc"));
    }

    /**
     * 串匹配算法 O(n*m)
     *
     * @param text
     * @param matchText
     * @return
     */
    private static List<Integer> matchVersion1(String text, String matchText) {
        boolean flag;
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < text.length(); i++) {
            flag = true;
            for (int j = 0; j < matchText.length(); j++) {
                if (text.charAt(i + j) != matchText.charAt(j)) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                list.add(i);
            }
        }
        return list;
    }


    /**
     * KMP
     * 若匹配到则将索引跳转到匹配之后的位置，匹配不到则索引跳转到未匹配之后的位置
     */
    private static List<Integer> matchVersion2(String text, String matchText) {
        int temp;
        int matchLength = matchText.length();
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < text.length(); ) {
            temp = -1;
            for (int j = 0; j < matchLength; j++) {
                if (text.charAt(i) != matchText.charAt(j)) {
                    if (j == 0) {
                        //若第一个字符匹配到,应该将位置移动1位,否则会造成死循环
                        //为什么不在for里面添加,是因为当在for中添加,若匹配到会造成少判断一个字符
                        temp = i + 1;
                    } else {
                        temp = i + j;
                    }
                    break;
                }
            }
            if (temp == -1) {
                list.add(i);
                i += matchLength;
            } else {
                i = temp;
            }
        }

        return list;
    }

    /**
     * 每次删除后,立马就插入.由于replace和matchText的文本长度可能不相同
     * 所以每次的删除,插入操作都会影响匹配索引位置的准确性
     * 因此在每次删除,插入操作都需要重新计算索引的位置
     * 索引位置的偏差也就是两个文本长度的偏差
     * 偏差在每一次迭代后都会增加一倍
     */
    private static String replace(String test, String matchText, String replace) {
        List<Integer> list = matchVersion2(test, matchText);
        StringBuilder stringBuilder = new StringBuilder(test);
        int length = matchText.length();
        int subLength = replace.length() - matchText.length();
        int loopCount = 0;
        for (int matchLocation : list) {
            stringBuilder.delete(matchLocation + subLength * loopCount, matchLocation + length + subLength * loopCount);
            stringBuilder.insert(matchLocation + subLength * loopCount, replace);
            loopCount++;
        }
        return stringBuilder.toString();
    }

    /**
     * 利用KMP的思想，一趟就可以实现替换
     * 若没有匹配到则将未匹配的串追加到result
     * 若匹配到则将matchText追加到result
     * @param text
     * @param matchText
     * @param replace
     * @return
     */
    private static String replaceTwo(String text, String matchText, String replace) {
        int temp;
        int matchLength = matchText.length();
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < text.length(); ) {
            temp = -1;
            for (int j = 0; j < matchText.length(); j++) {
                if (text.charAt(i + j) != text.charAt(j)) {
                    if (j == 0) {
                        temp = i + 1;
                    } else {
                        temp = i + j;
                    }
                    break;
                }
            }
            if (temp != -1) {
                //没有匹配到
                result.append(text.substring(i, temp));
                i = temp;
            } else {
                //匹配到
                result.append(replace);
                i += matchLength;
            }
        }
        return result.toString();
    }
}