RE: [xsl] Finding first difference between 2 text strings

[Hermann Stamm-Wilbrandt <STAMMW@xxxxxxxxxx>]

> If I weren't on vacation I would volunteer a solution using
> divide-and-conquer recursion: see if the first half of the two strings is
> the same, then split into quarters, etc.

Following that line below pure XSLT 1.0 stylesheet gives
the common prefix of two strings.
Mismatch position is just its string-length+1.

(Just in case of email-gateway modifications:
 http://www.stamm-wilbrandt.de/en/xsl-list/CommonPrefix.xsl)

<xsl:stylesheet version="1.0"
  xmlns:xsl="http://www.w3.org/1999/XSL/Transform";
>
  <xsl:output method="xml"/>

  <xsl:template name="CommonPrefix">
    <xsl:param name="a"/>
    <xsl:param name="b"/>

    <xsl:variable name="A" select="string-length($a)"/>.
    <xsl:variable name="B" select="string-length($b)"/>.

    <xsl:choose>
      <xsl:when test="$A &lt; $b">
        <xsl:call-template name="CommonPrefixRec">
          <xsl:with-param name="a" select="$a"/>
          <xsl:with-param name="b" select="substring($b,1,$A)"/>
        </xsl:call-template>
      </xsl:when>
      <xsl:otherwise>
        <xsl:call-template name="CommonPrefixRec">
          <xsl:with-param name="a" select="substring($a,1,$B)"/>
          <xsl:with-param name="b" select="$b"/>
        </xsl:call-template>
      </xsl:otherwise>
    </xsl:choose>
  </xsl:template>

  <xsl:template name="CommonPrefixRec">
    <xsl:param name="a"/>
    <xsl:param name="b"/>

    <xsl:variable name="mid" select="floor(string-length($a) div 2)"/>
    <xsl:variable name="a1" select="substring($a,1,$mid)"/>)
    <xsl:variable name="b1" select="substring($b,1,$mid)"/>)

    <xsl:choose>
      <xsl:when test="not(substring($a,1,1) = substring($b,1,1))"/>

      <xsl:when test="$a1 = $b1">
        <xsl:value-of select="$a1"/>
        <xsl:call-template name="CommonPrefixRec">
          <xsl:with-param name="a" select="substring($a,$mid + 1)"/>
          <xsl:with-param name="b" select="substring($b,$mid + 1)"/>
        </xsl:call-template>
      </xsl:when>

      <xsl:otherwise>
        <xsl:call-template name="CommonPrefixRec">
          <xsl:with-param name="a" select="substring($a,1,$mid)"/>
          <xsl:with-param name="b" select="substring($b,1,$mid)"/>
        </xsl:call-template>
      </xsl:otherwise>
    </xsl:choose>
  </xsl:template>


  <xsl:template match="/">
    <out>
      <xsl:call-template name="CommonPrefix">
        <xsl:with-param name="a" select="'abcdefghijklmnopqrstuvwxyz'"/>
        <xsl:with-param name="b" select="'abcdefghijklmnopqrstuvwxy0'"/>
      </xsl:call-template>
    </out>
  </xsl:template>

</xsl:stylesheet>



Mit besten Gruessen / Best wishes,

Hermann Stamm-Wilbrandt
Developer, XML Compiler
WebSphere DataPower SOA Appliances
----------------------------------------------------------------------
IBM Deutschland Research & Development GmbH
Vorsitzender des Aufsichtsrats: Martin Jetter
Geschaeftsfuehrung: Erich Baier
Sitz der Gesellschaft: Boeblingen
Registergericht: Amtsgericht Stuttgart, HRB 243294


                                                                           
             "Michael Kay"                                                 
             <mike@xxxxxxxxxxx                                             
             m>                                                         To 
                                       <xsl-list@xxxxxxxxxxxxxxxxxxxxxx>   
             09/11/2009 06:17                                           cc 
             PM                                                            
                                                                   Subject 
                                       RE: [xsl] Finding first difference  
             Please respond to         between 2 text strings              
             xsl-list@xxxxxxxx                                             
              lberrytech.com                                               
                                                                           
                                                                           
                                                                           
                                                                           





If I weren't on vacation I would volunteer a solution using
divide-and-conquer recursion: see if the first half of the two strings is
the same, then split into quarters, etc.

Regards,

Michael Kay
http://www.saxonica.com/
http://twitter.com/michaelhkay



> -----Original Message-----
> From: James A. Robinson [mailto:jim.robinson@xxxxxxxxxxxx]
> Sent: 11 September 2009 04:53
> To: xsl-list@xxxxxxxxxxxxxxxxxxxxxx
> Subject: Re: [xsl] Finding first difference between 2 text strings
>
> On Thu, 10 Sep 2009 20:41:21 -0700 I wrote:
> <
> < Wow, that's... very very impressive.  So you're replacing
> regular < expression values with placeholders in both
> strings, then wrapping ever < character in $bb with a regex
> expression, e.g., '(a)?', to finally < perform a regex
> replacement on $aa?  What does the leading colon < do?
>
> One last comment.  I timed 100 iterations comparing two 520
> character strings, and both functions run in effectively the
> same time, but your solution doesn't run into the stack
> overflow problem that mine does at the 520+ character range.
>
> Jim
>
> - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
> James A. Robinson                       jim.robinson@xxxxxxxxxxxx
> Stanford University HighWire Press      http://highwire.stanford.edu/
> +1 650 7237294 (Work)                   +1 650 7259335 (Fax)