Find first non-matching character between two strings

I'll use a numbers table. It can be used as an iterator over the two strings, but in a relational way.

My approach is to use the numbers table as an iterator over the strings, but in a relational way. The question calls for finding the first character in each string where they differ. The characters can be found using SUBSTRING(). Since we want the first difference we can use MIN() of the iterator. If no differences are found, i.e. the strings are equal, the checks on the lengths of the strings stop the iteration continuing to the end of the numbers table, which would be wasteful. I add one to the string length to catch the case where one string is a proper prefix of the other e.g. "interest" and "interested".

declare @FirstString    varchar(20) = 'interested';
declare @SecondString   varchar(20) = 'interesting';

select
    MIN(n.Number)
from dbo.Numbers as n
where SUBSTRING(@FirstString, n.Number, 1) <> SUBSTRING(@SecondString, n.Number, 1)
and n.Number <= LEN(@FirstString) + 1
and n.Number <= LEN(@SecondString) + 1;

If the strings are empty, equal or NULL this will return NULL.

With a clustered index on dbo.Numbers.Number the optimizer (in my instance - 2017 CU12) chooses to read the table in number order (Clustered Index Seek, Ordered = True). Further the predicate is pushed into the index seek. That operator processes 9 rows, the minimum required. The remainder of the plan simply returns the one row from dbo.Numbers which meets the query's requirements.

If the strings were very large, say DNA base pairs, and it was known that the matching prefixes were very long compared to the differing suffixes, it would be possible to invert the sequence. One could use REVERSE() on the strings. Placing a descending index on dbo.Numbers.Number and using MAX() may also work. Further testing would be required to prove a performance benefit, however.

With thanks to Andriy M for valuable observations.

First you should have a Numbers table.

create table dbo.Number(N int not null);
go

alter table dbo.Number add constraint PK_Number_N primary key clustered (N);

go

;with C(N) as
(
  select 0
  union all
  select N+1
  from C
  where N < 11000
)
insert into dbo.Number(N)
select N
from C
option (maxrecursion 0);

Use the numbers table to split your strings into rows. Get the matching characters and position using intersect. Use row_number to get only the matching characters from the start and finally rebuild the string with a for xml trick or string_agg.

declare @Str1 varchar(20) = 'Interesting0a';
declare @Str2 varchar(20) = 'Interested00a';

with C1 as
(
  select N.N,
         substring(@Str1, N.N, 1) as C
  from dbo.Number as N
  where N.N between 1 and len(@Str1)
  intersect
  select N.N,
         substring(@Str2, N.N, 1)
  from dbo.Number as N
  where N.N between 1 and len(@Str2)
),
C2 as
(
  select C1.N,
         C1.C,
         row_number() over(order by C1.N) as rn
  from C1
)
select string_agg(C2.C, '') within group(order by C2.N)
from C2
where C2.N = C2.rn;

/*
select (
       select C2.C as '*'
       from C2
       where C2.N = C2.rn
       order by C2.N
       for xml path(''), type
       ).value('text()[1]', 'varchar(20)');
*/

There is a very similar question on another forum in which somebody wants to compare varchar arrays 1 character at a time.

There are various answers there that include iterating through strings one character at a time, and lengthy scripts that introduce new tables of numbers into your database. And then there is a little gem of an answer that uses bit-wise comparison to detect the first difference between strings.

To do so, that solution converts each character of each string into binary representation. Due to the limit on the number of numerals permitted within the bigint data type there is the short note that this "is a nice function that works for up to 8 characters!"

Of course, extending this to support longer strings involves the trivial step of breaking the supplied strings into 8 character chunks - which is the solution I provide here.

create FUNCTION dbo.fnFirstDifference(@FirstString VARCHAR(256),@SecondString VARCHAR(256))
RETURNS int
AS
BEGIN
DECLARE @var VARBINARY(8),
@firstChunk varchar(8),
@secondChunk varchar(8),
@chunkStart int,
@loopCount int,
@pos TINYINT

set @chunkStart = 1
set @loopCount = -1;
set @pos = 0;

set @firstChunk = substring(@firstString, @chunkStart, 8);
set @secondChunk = substring(@secondString, @chunkStart, 8);

while @pos = 0 and (datalength(@firstChunk) > 0 or datalength(@secondChunk) > 0)
    begin

        SELECT @var = CAST(CAST(@FirstChunk AS BINARY(8)) AS BIGINT) ^ CAST(CAST(@SecondChunk AS BINARY(8)) AS BIGINT),
        @pos = PATINDEX('%[^0]%', SUBSTRING(master.dbo.fn_sqlvarbasetostr(@var), 3, 32)),
        @pos = (1 + @pos) / 2

        set @chunkStart = @chunkStart + 8;
        set @firstChunk = substring(@firstString, @chunkStart, 8);
        set @secondChunk = substring(@secondString, @chunkStart, 8);
        set @loopCount = @loopCount + 1;
    end

if @pos <> 0 set @pos = (@loopCount * 8) + @pos;

RETURN @pos
END

The original function returned a varchar providing all matching characters, plus the first non-matching character, from string 1, then a hyphen, and then likewise for string 2. For example: 'Interesti-Intereste'. I have converted this to provide the position of the first non-matching character - thus returning 9 for the following example:

 select dbo.fnFIrstDifference('Interesting', 'Interested')

Adapting to the other use cases is trivial.

I think you can translate this to a function

DECLARE @Str1 VARCHAR(45) = 'Interesting',
        @Str2 VARCHAR(45) = 'Interested';

WITH CTE AS
(
  SELECT 1 Num
  UNION ALL
  SELECT Num + 1
  FROM CTE
  WHERE Num < (SELECT CASE WHEN LEN(@Str1) > LEN(@Str2) THEN 
                                LEN(@Str1) 
                                ELSE LEN(@Str2)
                           END)
)
,
F AS
(
SELECT *, @Str1 Str1, @Str2 Str2,
       CASE WHEN SUBSTRING(@Str1, Num, 1) = SUBSTRING(@Str2, Num, 1) THEN 0
            ELSE 1
            END IsTheSame
FROM CTE
)
SELECT TOP 1 Num
FROM F
WHERE IsTheSame = 1
ORDER BY Num ASC
OPTION (MAXRECURSION 45); --For the function 300

Returns: 9

Live Demo

Live Demo For The Function

You can even remove the F cte and just create your function as

CREATE FUNCTION dbo.FindFirstDeff(
  @FirstStr VARCHAR(300),
  @SecondStr VARCHAR(300)
)
RETURNS INT
AS
BEGIN
  DECLARE @Value INT = -1;
  WITH CTE AS
  (
    SELECT 1 Num, @FirstStr Str1, @SecondStr Str2
    UNION ALL
    SELECT Num + 1, Str1, Str2
    FROM CTE
    WHERE Num < (SELECT CASE WHEN LEN(@FirstStr) > LEN(@SecondStr) THEN 
                                  LEN(@FirstStr) 
                                  ELSE LEN(@SecondStr)
                             END)
  )
  SELECT TOP 1 @Value =Num
  FROM CTE
  WHERE SUBSTRING(Str1, Num, 1) <> SUBSTRING(Str2, Num, 1)
  ORDER BY Num ASC
  OPTION (MAXRECURSION 300);

  RETURN(@Value);
END

Which will return for a sample data

+-------------+--------------+--------+
|    Str1     |     Str2     | Result |
+-------------+--------------+--------+
| Interesting | Interested   |      9 |
| Helping     | Helped       |      5 |
| anything    | unbelievable |      1 |
| Staying     | Stay         |      5 |
| abc         | abc          |     -1 |
+-------------+--------------+--------+

Check it out here

Good Solution depend upon how you ae going to use in real life and volume of data that will be process in one query.

TVF will be preferred in most cases.

declare @str1 varchar(50)='interested'
declare @str2 varchar(50)='interesting'

Method 1

Same number table will be as use by @Green.

My where condition is less complicated.

--find string with least length
declare @LeastLength int
IF (len(@str1) <= len(@str2))
    SET @LeastLength = len(@str1)
ELSE
    SET @LeastLength = len(@str2);

WITH CTE
AS (
    SELECT *
        ,CASE 
            WHEN SUBSTRING(@str1, number, 1) = SUBSTRING(@str2, number, 1)
                THEN 1
            ELSE 0
            END isEqual
    FROM tblnumber
    WHERE number <= @LeastLength
    )
SELECT TOP 1 number
FROM CTE
WHERE isEqual = 1
ORDER BY number DESC

Method 2 ,

using Recursive CTE in most cases loop number won't be more than 30.

;with CTE as
(
 select 1 rn, case when SUBSTRING(@str1,1,1)=SUBSTRING(@str2,1,1) then 1 else 0 end isEqual
 --,SUBSTRING(@str1,1,1) col1,SUBSTRING(@str2,1,1)col2
 UNION ALL
 select rn+1, case when SUBSTRING(@str1,rn+1,1)=SUBSTRING(@str2,rn+1,1) then 1 else 0 end isEqual
 --,SUBSTRING(@str1,rn+1,1) ,SUBSTRING(@str2,rn+1,1)
 FROM cte
 WHERE isEqual>0
)

--SELECT * FROM cte

--where isEqual=1

select top 1 rn from cte
where isEqual=1
order by rn desc

Number Table is very useful in other cases also. Method 1 is better.

Notice that no performance degarding window function is use.