一、相关概念

二、题目

题目

1
2

思路

KMP算法是求出子串在主串中第一次出现的位置，现在这个题是要找出子串在主串中出现的所有位置，然后将相应位置处的字符串进行替换。

代码

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class 字符串字符替换 {
    public static void main(String[] args) {
        new 字符串字符替换().exe();
    }
    
    private void exe(){
        Scanner scan=new Scanner(System.in);
        String str=scan.nextLine();
        String subStr=scan.nextLine();
        String destStr=scan.nextLine();
        // 子串在主串中出现的开始位置
        List<Integer> list=kmp_index(str,subStr);
        int len=subStr.length();
        for(int i=0;i<str.length();i++){
            if(list.contains(i)){
                // 输出目标串3
                int temp=0;
                while(temp<destStr.length()){
                    System.out.print(destStr.charAt(temp++));
                }
                // i往前跳转subStr的长度
                i+=(len-1);
            }else{
                System.out.print(str.charAt(i));
            }
        }
    }

    
    /**
     * 目的：保持i不动，通过调整j来消除i处的不匹配
     * 
     * @param str
     * @param subStr
     * @return
     */
    private List<Integer> kmp_index(String str, String subStr) {
        // next数组
        int[] next = getNext(subStr);
        // 主串
        char[] strArr = str.toCharArray();
        // 子串
        char[] subStrArr = subStr.toCharArray();
        int i = 0, j = 0;
        List<Integer> searchResult=new ArrayList<Integer>();
        while(i< str.length()){
            while (i < str.length() && j < subStr.length()) {
                if (strArr[i] == subStrArr[j]) {
                    // 该位相等
                    i++;
                    j++;
                } else {
                    // 不等：kmp的目标是i不动，通过调整j使得调整能够继续
                    j = next[j];
                    // 但是next数组中标记了一种特殊情况：那就是当next[x]=-1时表示此时应该：i++;j=0
                    if (j == -1) {
                        i++;
                        j = 0;
                    }
                }
            }
            if (j == subStr.length()) {
                // 说明子串在主串中
                searchResult.add(i - subStr.length());
            }
            j=0;
        }
        
        return searchResult;
    }

    /**
     * 得到next数组
     * 
     * @param subStr
     * @return
     */
    private int[] getNext(String subStr) {
        int n=subStr.length();
        int[] next = new int[n];
        next[0] = -1;
        char[] subStrArr = subStr.toCharArray();
        int i = 0, j = -1;
        while (i < n-1) {// 这里要i<n-1，一开始写的i<n导致最后数组越界了
            if ( (j == -1) || (subStrArr[i] == subStrArr[j]) ) {
                // j==-1时：从数组中取元素都要越界了，还不赶紧前进一位！！
                i++;
                j++;
                next[i] = j;
            } else {
                j = next[j];
            }
        }
        return next;
    }
}

参考文献

好未来 2019校园招聘 笔试编程题-2018.8.28