алгоритм поиска в массиве строк наиболее отличающуюся от первой

#cpp #массивы #алгоритм #поиск #сравнение

Я ищу наиболее быстрый алгоритм для поиска строки в массиве строк, которая сильнее
всего отличается от первой строки массива. Строки все одинаковой длины. Позиция символов
и их ASCII код имеет принципиальное значение. Если решать задачу в лоб, то нужно перебрать
каждую строчку массива и сравнить каждый ее символ с символом первой строки с тем же
индексом. Если они отличаются, то счетчик для этой строки массива увеличивается. Самый
большой счетчик дает нам строку, которая наиболее отличается от первой.
    

Ответы

Ответ 1

Можно использовать следующий алгоритм:

std::vector strings
...
std::vector distances;
for(size_t i = 1; i < strings.size(); ++i)
{
    std::deque tmp(strings[i].size());
    for(size_t j = 0; j < tmp.size(); ++j)
        tmp[j] = static_cast(strings[i][j] == strings[0][j]);
    auto distance = count(begin(tmp), end(tmp), false);
    distances.push_back(distance);
}
auto idx = distance(begin(distances), max_element(begin(distances), end(distances))) + 1;
auto result = strings[idx];


Этот код очень легко переписать под векторные инструкции и его скорость может вырасти
многократно, но для этого надо знать размер строк(Вы его знаете, я — нет)