|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Anton Maydell 2:5030/744.179 30 May 2003 16:15:03
To : Yuri Burger
Subject : Hечеткое сравнение строк
--------------------------------------------------------------------------------
30 May 03 14:28, you wrote to Alex Astafiev:
YB> Цель: дать оценку "похожести" двух строк [0,1]. Предполагается что
YB> одна из строк является "вариантом" другой, где
YB> пропущены/добавлены/исправлены некоторые символы.
IMHO, c помощью Динамического Программирования эта задача решается
за время O(n * m), где n и m - длины сравниваемых строк.
А приведённый тобой исходник зависает уже при n = m = 20.
Пример:
s1="qghwgeglsklfeotiurtf";
s2="qwirtkjtyjktreukjkry";
std::cout<<s1<<" = "<<s2<<" : "<<fuzzy::compare(s1,s2)<<std::endl;
std::cout<<s2<<" = "<<s1<<" : "<<fuzzy::compare(s2,s1)<<std::endl;
Hа acm.uva.es есть схожая задача 526.String Distance and Transform Process
(http://acm.uva.es/p/v5/526.html).
Ограничения : n,m <= 80.
Так её решили более 200 человек.
Anton
--- GoldED/W32 3.0.1-asa8
* Origin: (2:5030/744.179)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
