Need an efficient algorithm to implement String.replaceAll()

If you want to do incremental replacement, you can use an explicit appendReplacement/Tail loop to a StringBuffer (unfortunately no StringBuilder overloads as of yet).

Here's the idiom from the documentation:

 Pattern p = Pattern.compile(PATTERN);
 Matcher m = p.matcher(INPUT_SOURCE);

 StringBuffer sb = new StringBuffer();
 while (m.find()) {
     m.appendReplacement(sb, REPLACEMENT);
 }
 m.appendTail(sb);

 System.out.println(sb.toString());

This is pretty much how replaceAll is implemented.

The benefit of this method is that since you have full control over the replacement iteration, you don't have to store the entire output in memory at any given time as a potentially long String. You can incrementally build the output, flushing the StringBuffer content to the disk periodically. That is, using this method can be more memory efficient than using replaceAll.

(You can also do fancy replacements that is not supported by the current replacement syntax, e.g. toUpperCase() transformation).

Note that there is a request for enhancement for Matcher to be able to append to any Appendable. If granted, not only can you use StringBuilder, but you can also directly replace to e.g. a FileWriter.

Related questions

• in matcher.replace method,how to limit replace times?
  • Has example of limited replacement and case transformation
• StringBuilder and StringBuffer in Java

See also

• BugID 5066679: Matcher should make more use of Appendable
  • If granted, this request for enhancement would allow Matcher to append to any Appendable