"Похожие" строки

[TemaTre]

Ребят как сравнить 2 строки на схожесть. Продолжаю свой вопрос по поводу распарсивания строки адреса. Теперь возникла другая проблема необходимо удалить схожие линки. скажем если есть 2 строки http://vk.com/id11111 и http://vk.com/id222222 нужна функция которая скажет на сколько эти строки похожи ну например в процентах. И если эти строки схожи на 60-80% то можно считать что это ссылки ссылаются на аналогичные странички...

[Bepec]

Эм... Неужели вы так не хотите думать собственной головой?

Вам же, если не изменяет память, давали даже ссылку на вики.

Разбивайте адрес по его структуре. И сравнивайте его части. Сошлось 4 из 5? Возможно ведёт на 1 и ту же страницу. Но уверенности нету и не будет.

Как вариант проверяйте куда вас приведёт по этой ссылке. И сранивайте уже результат перехода.

PS ленивец.

[sudo]

Расстояние Левенштейна должно помочь

http://ru.wikipedia.org/wiki/%D0%A0%D0%B0%D1%81%D1%81%D1%82%D0%BE%D1%8F%D0%BD%D0%B8%D0%B5_%D0%9B%D0%B5%D0%B2%D0%B5%D0%BD%D1%88%D1%82%D0%B5%D0%B9%D0%BD%D0%B0

Код

C++ (Qt)
int levenshteinDistance(const QString& s1, const QString& s2)
{
  const int len1 = s1.size();
  const int len2 = s2.size();
 
  QVector<int> col(len2 + 1);
  QVector<int> prevCol(len2 + 1);
 
  for (int i = 0; i < prevCol.size(); ++i)
    prevCol[i] = i;
 
  for (int i = 0; i < len1; ++i)
  {
    col[0] = i + 1;
    for (int j = 0; j < len2; ++j)
      col[j + 1] = qMin(qMin(col[j] + 1, prevCol[j + 1] + 1), prevCol[j] + (s1[i] == s2[j] ? 0 : 1));
    prevCol = col;
  }
 
  return prevCol[len2];
}