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),
@jjMax=len(@SecondString),
@index=@jjMax+1
Select @ArrayMax=(@iiMax)*(@jjMax)
Select @Array=replicate(char(0), @jjMax+1)
Select
@Index=@Index+case when (number-1) % @jjMax = 0 then 2 else 1 end,
@west=case when (number-1) % @jjMax = 0 then Char(0) else substring(@Array,@index-1,1) end,
@Array=@Array
+ case when (number-1) % @jjMax = 0 then Char(0) else '' end
+ case
when substring(@firstString,((Number-1)/@jjMax)+1,1)
=substring(@SecondString, ((number-1)% @jjMax)+1 ,1)
then Char(Ascii(substring(@Array,@index-@jjmax-2,1))+1)
when Ascii(substring(@Array,@index-@jjmax-1,1))>ascii(@west)
then substring(@Array,@index-@jjmax-1,1)
else @west
end
from numbers where number<=@ArrayMax
Declare @commonString Varchar(max), @X_Y int
Select @CommonString =''
Select @ii=@iimax+1,@jj=@jjmax+1
while (@ii>1 and @jj>1)
begin
Select @X_Y = ((@ii-1)*(@jjMax+1))+@jj
if (substring(@firststring,@ii-1,1) = substring(@Secondstring,@jj-1,1))
BEGIN
Select @CommonString=@CommonString+substring(@firststring,@ii-1,1)
select @jj=@jj-1, @ii=@ii-1
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
Telegram: DB developers channel