Consequtive letter matches...please help

5 Jul 2006 4:22 PM

almurph@altavista.com

Hi,

        Hope you can help me. This is a trick one - at least I think
so. I
have 2 strings. I have to calculate the "score" of the strings. Score
is determined by matching patterns of letters within the strings.
Essentially it is the sum of the consequtive letter matches.

        Here are the rules of score:

1. Start at the end of the shorter string and and add up the amount of
letters found in the same order in the longer string. Continue for all
letters in the shorter string
2. I think that you may have to work from the end of the longer string
also
3. If strings are equal - pick either, note that the answer should be
the same regardless of which strings is compared against which.

        As you can see the maximum value of score could be the length
of the
shortest string (in this case the shorter string is identical to the
longer, like a subset)

Simple Worked Example:

String1: "My name is John"
String2: "My name is Johnson"

        Score = 12 (for "name isJohn") + 3 (for "My") = 15

Can anyone help me with coding this algorithm please?
Comments/sample-code greatly appreciated. Is this a well known string
matching algorithm?

Thank you,
Al.

5 Jul 2006 6:28 PM

Terry

I am not sure that I understand the rule. You say it is "add up the amount of
letters found in the same order in the longer string. Continue for all
letters in the shorter string", but that is not what you do in your example.
There the score is the length of the largest substring (in the shorter of
the 2 comparison strings) found in the other string. In either case, it is
not a difficult algorithm to program. Think of using a couple of nested For
loops and using the InStr function.

--
Terry

Show quoteHide quote

"almu***@altavista.com" wrote:

> Hi,
>
>         Hope you can help me. This is a trick one - at least I think
> so. I
> have 2 strings. I have to calculate the "score" of the strings. Score
> is determined by matching patterns of letters within the strings.
> Essentially it is the sum of the consequtive letter matches.
>
>
>         Here are the rules of score:
>
>
> 1. Start at the end of the shorter string and and add up the amount of
> letters found in the same order in the longer string. Continue for all
> letters in the shorter string
> 2. I think that you may have to work from the end of the longer string
> also
> 3. If strings are equal - pick either, note that the answer should be
> the same regardless of which strings is compared against which.
>
>
>         As you can see the maximum value of score could be the length
> of the
> shortest string (in this case the shorter string is identical to the
> longer, like a subset)
>
>
> Simple Worked Example:
>
>
> String1: "My name is John"
> String2: "My name is Johnson"
>
>
>         Score = 12 (for "name isJohn") + 3 (for "My") = 15
>
>
> Can anyone help me with coding this algorithm please?
> Comments/sample-code greatly appreciated. Is this a well known string
> matching algorithm?
>
>
> Thank you,
> Al.
>
>

6 Jul 2006 1:02 PM

Phill W.

almu***@altavista.com wrote:

> 1. Start at the end of the shorter string and and add up
> the amount of letters found in the same order in the longer string.
> Continue for all letters in the shorter string

Now, do you mean the same "order", or the same actual characters, in the
same position that they appear in the original string?
To do the latter, you'd have something like

Function Score( _
   ByVal s1 as String _
, ByVal s2 as String _
) as Integer

    Dim iSub as Integer

    For iSub = 1 To Len( s1 )
       If Mid$( s1, 1 ) <> " " Then
          If Mid$( s1, 1 ) <> Mid$( s2, 1 ) Then
             Score = ( iSub - 1 )
             Exit Function
          End If
       End If
    Next

    Score = Len( Replace( s1, " ", "" ) )
End Function

The above will count the matching /letters/, ignoring spaces.

> Is this a well known string matching algorithm?

I've never come across it before... ;-)

HTH,
Phill W.