Given a text and a pattern. Replace all the occurrences of the pattern in the text by another given string.

For Example: If text = “aabaabab” and pattern = “ab”. Then after replacing pattern in the text by “abc” the output should be “aabcaabcabc”.

The trivial solution would be to do a brute-force search of the pattern in the text in order to find all the occurrences of the pattern in the text. One we have all the positions where the pattern is found in the text then we simply replace the pattern by the given string. This is a O(n^2) algorithm.

How to improve this solution? Note that the key step here is to find the positions where pattern is found in the test. So, we can use the KMP algorithm to find all the occurrences of the second string (pattern) in the first string (text) in O(n). I have posted the KMP algorithm in a separate post.

So, we will use the KMP algorithm to find all the occurrences of the second string (pattern) in the first string (text) in O(n). Save these positions into an array of integers (lets say positionArray). We will use a StringBuilder to construct the replaced string. Also We need to keep a pointer to the first index of the position array (lets say positionPointer).

Scan the text from left to right and append the character in current position into the string builder except for the position where the positionPointer is currently pointing to in the positionArray, in which case we append the given string (replace string) in the string builder and skip the whole pattern in the text from current scan position.

Once we’ve replaced the string we need to increment the positionPointer to skip the overlapping pattern positions (research this example: text=”aaaaaa”, pattern = “aa”, replaceWith = “X”). We can do it by aligning the positionPointer with the scan index.

The overall operation is O(n) time and O(n) space. Below is a pseudocode using KMP_SEARCH I have discussed in another post.

public String replace(final String text, final String pattern, final String replaceWith) throws Exception {
    if (text.equals(pattern)) {
        return replaceWith;
    }
    if (pattern == null || pattern.isEmpty() || replaceWith == null || replaceWith.isEmpty()) {
        return text;
    }

    final List<Integer> positions = KMPSearch(text, pattern);
    final int[] substringPositions = new int[positions.size()];
    int positionPointer = 0;
    for (final int pos : positions) {
        substringPositions[positionPointer++] = pos;
    }
    positionPointer = 0;

    final StringBuilder replacedString = new StringBuilder();
    final char[] textChars = text.toCharArray();

    for (int i = 0; i < textChars.length; i++) {
        while (positionPointer < substringPositions.length && i > substringPositions[positionPointer]) {
            positionPointer++;
        }

        if (positionPointer < substringPositions.length && i == substringPositions[positionPointer]) {
            replacedString.append(replaceWith);
            i += pattern.length() - 1;
        } else {
            replacedString.append(textChars[i]);
        }
    }

    return replacedString.toString();
}