Title: Fast method to repeat a string
Submitter: Mats Kindahl (other recipes)
Last Updated: 2002/09/10
Version no: 1.0
Category: String manipulation

Description:

A recursive template to repeat a string a number of times in a manner similar to the Perl 'x' operator.

Source: Text Source

<!-- Repeat the string 'str' 'cnt' times -->
<xsl:template name="repeat-string">
  <xsl:param name="str"/><!-- The string to repeat -->
  <xsl:param name="cnt"/><!-- The number of times to repeat the string -->
  <xsl:param name="pfx"/><!-- The prefix to add to the string -->
  <xsl:choose>
    <xsl:when test="$cnt = 0">
      <xsl:value-of select="$pfx"/>
    </xsl:when>
    <xsl:when test="$cnt mod 2 = 1">
      <xsl:call-template name="repeat-string">
	  <xsl:with-param name="str" select="concat($str,$str)"/>
	  <xsl:with-param name="cnt" select="($cnt - 1) div 2"/>
	  <xsl:with-param name="pfx" select="concat($pfx,$str)"/>
	</xsl:call-template>
    </xsl:when>
    <xsl:otherwise>
	<xsl:call-template name="repeat-string">
	  <xsl:with-param name="str" select="concat($str,$str)"/>
	  <xsl:with-param name="cnt" select="$cnt div 2"/>
	  <xsl:with-param name="pfx" select="$pfx"/>
	</xsl:call-template>
    </xsl:otherwise>
  </xsl:choose>
</xsl:template>

The license for this recipe is available here.

Discussion:

The template is written recursively and uses the "binary method" to repeat the string in O(log n) time. The actual number of concat operations performed to repeat a string n times is log n + .