Анализ строк, алгоритм Хиршберга

[kurkova]

Помогите, пожалуйста, написать функцию для рассчета алгоритма Хиршберга.
http://program.rin.ru/cgi-bin/print.pl?id=863
en.wikipedia.org/wiki/Hirschberg's_algorithm

То есть берем две ячейки в Excel и при помощи функции рассчитываем меру близости между ними, в алгоритме Хиршберга - нахождение наибольшей общей подпоследовательности.

Есть пример, как реализовано расстояние Левенштейна:
Здесь ArrN - функция, которая обрезает пробелы и переводит строку в нижний регистр.

Public Function Levenshtein(prmT1 As String, prmT2 As String) As Long
'вычисляем расстояние Левенштейна между 2умя преобразованными строками
prmT11 = ArrN(prmT1)
prmT21 = ArrN(prmT2)
Dim D() As Long
M = Len(prmT11)
N = Len(prmT21)
ReDim D(M, N)
D(0, 0) = 0
For j = 1 To N
  D(0, j) = D(0, j - 1) + 1 ' Вставка
Next j
For i = 1 To M
  D(i, 0) = D(i - 1, 0) + 1 ' Удаление
  For j = 1 To N
  'D(i, j) = Min(D(i - 1, j) + Ci, D(i, j - 1) + Cd, D(i - 1, j - 1) + Cr)
  'Ci - цена вставки, Cd - цена удаления, Cr - цена замены
    D(i, j) = D(i - 1, j) + 1
    If D(i, j) > D(i, j - 1) + 1 Then D(i, j) = D(i, j - 1) + 1
    Cr = IIf(Mid(prmT11, i, 1) <> Mid(prmT21, j, 1), 1, 0)
    If D(i, j) > D(i - 1, j - 1) + Cr Then D(i, j) = D(i - 1, j - 1) + Cr
    If i > 1 And j > 1 Then
       Ct = IIf(Mid(prmT11, i, 1) = Mid(prmT21, j - 1, 1) And Mid(prmT11, i - 1, 1) = Mid(prmT21, j, 1), 1, 10 ^ 3)
       If D(i, j) > D(i - 2, j - 2) + Ct Then D(i, j) = D(i - 2, j - 2) + Ct
    End If
   Next j
Next i
Levenshtein = D(M, N)
End Function

Заранее спасибо за помощь.

[boa]

LTrim, RTrim, and Trim Functions
Returns a Variant (String) containing a copy of a specified string without leading spaces (LTrim), trailing spaces (RTrim), or both leading and trailing spaces (Trim).
- что бы оборезать справа/слева(из хэлпа)

LCase() и UCase() — перевести строку в нижний/ерхний регистры. Часто используется для подготовки значения к сравнению, когда при сравнении регистр не важен (фамилии, названия фирм, городов и т.п.).

[exceleved]

"Хиршберг", "Левенштейн"... наши ребята уже все сделали
http://www.planetaexcel.ru/forum.php?thread_id=22556

[kurkova]

Спасибо! Мне это пригодилось.