compare two strings - - - for the guru's

[vonclausowitz]

Hi Everyone,

This is a very complicated, if not impossible problem.
I have two strings I want to compare. The problem is that somewhere in
both strings there is a text which is identical, but it's never on the
left or right.

example:
string1 = "THIS ---- MY.NEW.FILE.OF.TODAY."
string2 = "MY.NEW.FILE.OF.TODAY.AND.TOMORROW."

the similarity is of course the part saying:
"MY.NEW.FILE.OF.TODAY."

I need a code getting me this part of the string.

Whooh..... ain't that though.

Marco

[Brian Wilson]

<vo***********@gmail.com> wrote in message
news:11*********************@g47g2000cwa.googlegro ups.com...

Hi Everyone,

This is a very complicated, if not impossible problem.
I have two strings I want to compare. The problem is that somewhere in
both strings there is a text which is identical, but it's never on the
left or right.

example:
string1 = "THIS ---- MY.NEW.FILE.OF.TODAY."
string2 = "MY.NEW.FILE.OF.TODAY.AND.TOMORROW."

the similarity is of course the part saying:
"MY.NEW.FILE.OF.TODAY."

I need a code getting me this part of the string.

Whooh..... ain't that though.

Marco

That is one similarity. Others are:
MY
NEW
FILE.OF.TODAY
A
N
So are you saying you are only looking for only the longest string which is
both of part of String1 and String2? What happens if String1="cats like
dogs" and String2="dogs like cats"? Would the function return "dogs" or
"cats" or possibly an array containing both?

[Salad]

vo***********@gmail.com wrote:

Hi Everyone,

This is a very complicated, if not impossible problem.
I have two strings I want to compare. The problem is that somewhere in
both strings there is a text which is identical, but it's never on the
left or right.

example:
string1 = "THIS ---- MY.NEW.FILE.OF.TODAY."
string2 = "MY.NEW.FILE.OF.TODAY.AND.TOMORROW."

the similarity is of course the part saying:
"MY.NEW.FILE.OF.TODAY."

I need a code getting me this part of the string.

Whooh..... ain't that though.

Marco

It would appear you need to do some loops. I might do something like
this... create string3 and string4. String3 would change all characters
not alph or space in string1 to a space. String4, from string2, same
thing.

comp s2 to s4. Same? Then no change, both equal.
No same? Then get into a loop.
First, comp loop would be for the following
"This My New File Of Today"
"This My New File Of"
"This My New File"
"This My New"
"This My"
"This"
Break on any that were found. If not, remove the first word and try again
"My New File Of Today"
"My New File Of"
"My New File"
"My New"
"My"
Break on any that were found. If not, remove the next first word and
try again
"New File Of Today"
"New File Of"
"New File"
"New"
and so on....

You should be able to use the following functions and command
Do While
For Next
Instr()
Mid()
Left()
Right()

The reason I removed anything not alpha is that I wanted spaces to
delimit words. When you have found the word, with
Instr(string4,string3) you will get the position. Then all you need is
to go to that position in string2 for the length of string3 to get the
corresponding value. You'll now know the common phrase between the two.

By going from longest string to shortest string you should get the
longest string between the two.

[Malcolm Cook]

your problem is stated: http://en.wikipedia.org/wiki/Longest...string_problem

the following function which appears to solve it was snarfed from :
http://www.planetsourcecode.com/vb/s...54427&lngWId=1

Public Function LongestCommonSubstring(A As String, B As String) As String
Dim sLenA, sLenB, sLen, i, j, idxA, idxB As Integer

sLenA = Len(A): sLenB = Len(B)
ReDim ArrLCS(0 To sLenA, 0 To sLenB) As Integer

For i = 1 To sLenA
For j = 1 To sLenB
If UCase$(Mid$(A, i, 1)) <> UCase$(Mid$(B, j, 1)) Then
ArrLCS(i, j) = 0
Else
ArrLCS(i, j) = 1 + ArrLCS(i - 1, j - 1)
If ArrLCS(i, j) > sLen Then
sLen = ArrLCS(i, j)
idxA = i: idxB = j
End If
End If
Next
Next

LongestCommonSubstring = Mid$(A, idxA - sLen + 1, ArrLCS(idxA, idxB))
Erase ArrLCS
End Function

[Brian Wilson]

"Malcolm Cook" <me*@stowers-institute.org> wrote in message
news:_h***************@news.more.net...

your problem is stated:
http://en.wikipedia.org/wiki/Longest...string_problem

the following function which appears to solve it was snarfed from :
http://www.planetsourcecode.com/vb/s...54427&lngWId=1

Public Function LongestCommonSubstring(A As String, B As String) As String
Dim sLenA, sLenB, sLen, i, j, idxA, idxB As Integer

sLenA = Len(A): sLenB = Len(B)
ReDim ArrLCS(0 To sLenA, 0 To sLenB) As Integer

For i = 1 To sLenA
For j = 1 To sLenB
If UCase$(Mid$(A, i, 1)) <> UCase$(Mid$(B, j, 1)) Then
ArrLCS(i, j) = 0
Else
ArrLCS(i, j) = 1 + ArrLCS(i - 1, j - 1)
If ArrLCS(i, j) > sLen Then
sLen = ArrLCS(i, j)
idxA = i: idxB = j
End If
End If
Next
Next

LongestCommonSubstring = Mid$(A, idxA - sLen + 1, ArrLCS(idxA, idxB))
Erase ArrLCS
End Function

That's a pretty compact solution and nicely answers my question what happens
if String1="cats like dogs" and String2="dogs like cats" - would the
function return "dogs" or "cats"?
Answer: neither, you idiot. It returns "s like "

[vonclausowitz]

Fantastic code.

Just changed the Strings in Variants so you can use a sStrA and sStrB
instead of already having to fillin a string.

Marco

[Tom van Stiphout]

On Fri, 7 Oct 2005 20:05:55 +0000 (UTC), "Brian Wilson"
<bw*****@ease.co.uk> wrote:

See: cats don't like dogs.

-Tom.

"Malcolm Cook" <me*@stowers-institute.org> wrote in message
news:_h***************@news.more.net...

your problem is stated:
http://en.wikipedia.org/wiki/Longest...string_problem

the following function which appears to solve it was snarfed from :
http://www.planetsourcecode.com/vb/s...54427&lngWId=1

Public Function LongestCommonSubstring(A As String, B As String) As String
Dim sLenA, sLenB, sLen, i, j, idxA, idxB As Integer

sLenA = Len(A): sLenB = Len(B)
ReDim ArrLCS(0 To sLenA, 0 To sLenB) As Integer

For i = 1 To sLenA
For j = 1 To sLenB
If UCase$(Mid$(A, i, 1)) <> UCase$(Mid$(B, j, 1)) Then
ArrLCS(i, j) = 0
Else
ArrLCS(i, j) = 1 + ArrLCS(i - 1, j - 1)
If ArrLCS(i, j) > sLen Then
sLen = ArrLCS(i, j)
idxA = i: idxB = j
End If
End If
Next
Next

LongestCommonSubstring = Mid$(A, idxA - sLen + 1, ArrLCS(idxA, idxB))
Erase ArrLCS
End Function

That's a pretty compact solution and nicely answers my question what happens
if String1="cats like dogs" and String2="dogs like cats" - would the
function return "dogs" or "cats"?
Answer: neither, you idiot. It returns "s like "

[Bruce Rusk]

It would return "like"

"Brian Wilson" <bw*****@ease.co.uk> wrote in message
news:di**********@nwrdmz03.dmz.ncs.ea.ibs-infra.bt.com...

<vo***********@gmail.com> wrote in message
news:11*********************@g47g2000cwa.googlegro ups.com...

Hi Everyone,

This is a very complicated, if not impossible problem.
I have two strings I want to compare. The problem is that somewhere in
both strings there is a text which is identical, but it's never on the
left or right.

example:
string1 = "THIS ---- MY.NEW.FILE.OF.TODAY."
string2 = "MY.NEW.FILE.OF.TODAY.AND.TOMORROW."

the similarity is of course the part saying:
"MY.NEW.FILE.OF.TODAY."

I need a code getting me this part of the string.

Whooh..... ain't that though.

Marco

That is one similarity. Others are:
MY
NEW
FILE.OF.TODAY
A
N
So are you saying you are only looking for only the longest string which
is both of part of String1 and String2? What happens if String1="cats
like dogs" and String2="dogs like cats"? Would the function return "dogs"
or "cats" or possibly an array containing both?

[Brian Wilson]

"Bruce Rusk" <br***************@stanford.edoo> wrote in message
news:di**********@news.Stanford.EDU...

It would return "like"

As I pointed out earlier, it acually returns "s like "