Find first non-matching character between two strings

Posting this with solution provided.

The use case could be framed in a number of ways:

• Return all characters that match at the start of two strings, until they do not match
• How many characters match between two strings before one character doesn't match?
• What is the first character that doesn't match between two strings?
• etc.

For example:

If I have the strings 'Interesting' and 'Interested' they are similar for all the characters 'Interest' and then the first string ends in 'ing' while the second ends in 'ed'. Therefore, they have 8 characters in common, the first non-matching character is the 9th and the identical string is 'Interest'.

For the question in the title, the first non-matching character is number 9.

• Are you concerned about performance on large datsets, or is this just a thought exercise? Mar 22 '19 at 11:52

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()', 'varchar(20)');
*/
• As I noted in the supplied answer, the linked example provides various solutions, including the use of a numbers table. What makes the alternate solution novel is the use of bit-wise comparison. Mar 27 '19 at 2:58

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.

• As I noted in the supplied answer, the linked example provides various solutions, including the use of a numbers table. What makes the alternate solution novel is the use of bit-wise comparison. Mar 27 '19 at 2:58

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.

• Bad idea to use WHILE loop as it perform so slow. Mar 22 '19 at 11:17
• @Sami - in my use case I am performing a single check against a couple of strings about 200 characters each, so performance is adequate. Someone else made a comment about comparing DNA base pairs - in that context, and over thousands of rows, perhaps not so good. I note you've contributed answers involving recursive functions - but are these faster than simply breaking the input strings into 8 char chunks? The key point about this solution is the novel use of bit-wise comparison. Mar 27 '19 at 2:57

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.