Как сделать умный поиск по списку

182

17 июня 2021, 15:00

Есть класс DB

class DB
    {
        public string Tovar { get; set; }
        public string Mnn { get; set; }
    }

Стоит задача составить умный поиск по List<DB>. Думал использовать расстояние Левенштейна. Но чем оно не нравится. Если исходное слово приветмосквасегоднявсехорошо и если сравнивать его со словом "все" мы получаем расстояние Левенштейна очень большое. Как объединить расстояние Левенштейна и Сontains? Я бы мог использовать просто Contains, но может быть так что искомое слово может быть ,например, всея.

Answer 1

Быстрый пример, хочу показать только идею. Код можно ускорить и я не смотрел крайние случае вообще

private bool SmartContains(string s1, string s2)
{
    if (s1.Length < s2.Length) return SmartContains(s2, s1);
    for(int i=0; i<=(s1.Length - s2.Length); i++)
    {
        int difs = 0;
        for(int j=0; j<s2.Length; j++)
        {
            if (s1[i+j] != s2[j]) difs++;
            if (difs > 1) break;
        }       
        if (difs<=1) return true;
    }
    return false;   
}

Код работает за квадратичное время, но его, по идее, можно ускорить. Пример использования

Console.WriteLine(SmartContains("приветземлясвамия1", "зимля"));
Console.WriteLine(SmartContains("приветземлясвамия1", "зимляz"));
Console.WriteLine(SmartContains("зимляz", "зимляz"));

Вывод