text: IF OBJECT_ID (N'LongestCommonSubsequence') IS NOT NULL
     DROP FUNCTION LongestCommonSubsequence
  GO
   
  Create FUNCTION LongestCommonSubsequence
  /**
  summary:   >
   The longest common subsequence (LCS) problem is the problem of finding the
   longest subsequence common to all sequences in two sequences. It differs
   from problems of finding common substrings: unlike substrings, subsequences
   are not required to occupy consecutive positions within the original
   sequences. For example, the sequences "1234" and "1224533324" have an LCS
   of "1234":
  Author: Phil Factor
  Revision: 1.0
  date: 05 Dec 2014
  example:
   code: |
       Select dbo.LongestCommonSubsequence ('1234', '1224533324')
       Select dbo.LongestCommonSubsequence ('thisisatest', 'testing123testing')
       Select dbo.LongestCommonSubsequence ( 'XMJYAUZ', 'MZJAWXU') 
       Select dbo.LongestCommonSubsequence ( 'beginning-middle-ending',
         'beginning-diddle-dum-ending')
  returns:   >
    the longest common subsequence as a string
  **/    
  (
   @firstString Varchar(max),
   @SecondString Varchar(max)
  )
  RETURNS varchar(max)
  as begin
   
  Declare @Array Varchar(MAX)
  Declare @ArrayMax int
  Declare @west char(1)
  Declare @Lines Varchar(max)
  Declare @ii int, @jj int, @iiMax int, @jjMax int, @index int
   
  Select @iiMax=len(@FirstString), --the length of the first string
         @jjMax=len(@SecondString), --the length of the second string
         @index=@jjMax+1 --where the first new item (matrix has an extra row & column)
  Select @ArrayMax=(@iiMax)*(@jjMax)--total length of the array iterated 
  Select @Array=replicate(char(0), @jjMax+1) --add in the first nought-filled row
   
  Select 
    @Index=@Index+case when (number-1) % @jjMax = 0 then 2 else 1 end, --current index
    @west=case when (number-1) % @jjMax = 0 then Char(0) else substring(@Array,@index-1,1) end,
    --as we add an extra column in, this is a dangerous operation otherwise
    @Array=@Array --we add a character to the string array, Char(0)--char
          + case when (number-1) % @jjMax = 0 then Char(0) else '' end -- begin new row always zero
          + case --check first to see if there was a match. If so, take north west number incremented
              when substring(@firstString,((Number-1)/@jjMax)+1,1)
                               =substring(@SecondString, ((number-1)% @jjMax)+1 ,1)
              --remember to set the appropriate collation for this comparison!
             then  Char(Ascii(substring(@Array,@index-@jjmax-2,1))+1)--increment the NW value 
           when Ascii(substring(@Array,@index-@jjmax-1,1))>ascii(@west) --compare west to north
             then substring(@Array,@index-@jjmax-1,1) --and take the larger
           else @west-- number to west if larger
          end
  from numbers where number<=@ArrayMax
   
  --Now all we need to do is to backtrack through the matrix to find the best solution
  Declare @commonString Varchar(max), @X_Y int
  Select @CommonString ='' --this contains the string
  Select @ii=@iimax+1,@jj=@jjmax+1
  while (@ii>1 and @jj>1) 
    begin
    Select @X_Y = ((@ii-1)*(@jjMax+1))+@jj --the current matrix location
    if (substring(@firststring,@ii-1,1) = substring(@Secondstring,@jj-1,1))
         BEGIN --if there is a match, add the character (we'll reverse it later)
      Select @CommonString=@CommonString+substring(@firststring,@ii-1,1)
      select @jj=@jj-1, @ii=@ii-1 --go north-west
      end
    else if ascii(Substring(@Array,@X_Y,1)) = ascii(Substring(@Array, @X_Y-@jjMax-1, 1))
      select @ii=@ii-1
    ELSE if ascii(Substring(@Array,@X_Y,1)) = ascii(Substring(@Array, @X_Y-1, 1))
      select @jj=@jj-1
    else break  
    if @@error>0 break   
    end
   return  Reverse(@CommonString)
   end
  go
   
  Declare @timing datetime Select @Timing=GetDate()
   
  if dbo.LongestCommonSubsequence ('1234', '1224533324')<>'1234' 
     raiserror('test 1 failed',16,1)
  if dbo.LongestCommonSubsequence ('thisisatest', 'testing123testing')<>'tsitest' 
     raiserror('test 2 failed',16,1)
  if dbo.LongestCommonSubsequence ('XMJYAUZ', 'MZJAWXU')<>'MJAU'
     raiserror('test 3 failed',16,1)
  if dbo.LongestCommonSubsequence ('yab', 'xabyrbyab')<>'yab'
     raiserror('test 4 failed',16,1)
  if dbo.LongestCommonSubsequence ('beginning-middle-ending','beginning-diddle-dum-ending')
     <>'beginning-iddle-ending' raiserror('test 5 failed',16,1)
   
  select datediff(millisecond,@timing,GetDate()) as milliseconds