How to Generate a String from a String Template in Java?

I want my Java App to read a String from a User, the String may contains some tags, for example :

String text = " value 1 = #value1 and value 2 = #value2 ";
int[] intArray = new int[] {4,5};

Also the user will enter an array of values to the application. As a programmer I don't know the exact number of values in the String. and I want to programatically generate this String :

String result = " value 1 = 4 and value 2 = 5 "

to do so I've implemented a method that search for the #value* regex and replace it with the first element in a stack of values. it Loops until the program cannot find any #value in the primary String, the problem is that for big Texts, the program take too much time to get executed, which is normal considering the approach adopted.

I've also heard of some Templating techniques using Velocity and FreeMarker, but I've never used them ( any clarification in this point is very welcome ).

So my question is : what is the best way to solve this problem (shortest execution time)?

PS : I don't need code, I want just an approach or API that may solve this issue.

If you are creating a new complete String at each replacement you will indeed run into problems. You can try building a StringBuffer as you go using the helper methods from Matcher instead. This should be much faster for large inputs:

String text = " value 1 = #value1 and value 2 = #value2 ";
int[] intArray = new int[] { 4, 5 };
Pattern p = Pattern.compile("#value(\\d+)");
Matcher m = p.matcher(text);
StringBuffer result = new StringBuffer();
while (m.find()) {
    m.appendReplacement(result, String.valueOf(intArray[Integer.parseInt(m.group(1)) - 1]));
}
m.appendTail(result);
System.out.println(result.toString());

EDIT
A number of people have pointed out that StringBuilder is better suited for this job. I agree, but unfortunately the Matcher API doesn't accept StringBuilder as argument to the appendReplacement() and appendTail() methods.