4

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

7
  • 6
    А намного скорее у вас не получится. Вам всё равно нужно сравнить все строки с первой. Единственное мелкое улучшение — вы можете запомнить текущее «наибольшее» расстояние, и если для следующей строки вы видите, что его уже достигнуть невозможно (слишком много одинаковых символов), прекратить сканирование этой строки.
    – VladD
    12 мар 2016 в 19:10
  • Забыл уточнить, все строки одинаковой длины и принципиально важна позиция символов в ней. 12 мар 2016 в 19:13
  • Уточните это, внеся правку в вопрос. Большинство здесь не читает чужие комментарии.
    – Max ZS
    12 мар 2016 в 19:14
  • Укажите критерий отличия строк.
    – Cerbo
    12 мар 2016 в 20:36
  • Вроде из задачи понятно, что мне важно, чтобы символы с одним и тем же индексом не совпадали? Или предложите как стоит переформулировать сам вопрос, чтобы это было понятно. 12 мар 2016 в 20:40

1 ответ 1

3

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

std::vector<std::string> strings
...
std::vector<size_t> distances;
for(size_t i = 1; i < strings.size(); ++i)
{
    std::deque<bool> tmp(strings[i].size());
    for(size_t j = 0; j < tmp.size(); ++j)
        tmp[j] = static_cast<char>(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];

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

2
  • У меня в проекте длина этих строк задается константой которая кратна трем и четырем. Величины порядка 12000 символов. С точной длиной еще не определились. Скажите, почему нужно знать размер строк, и если вам не трудно, приведите пример использования векторных инструкций? 27 мар 2016 в 17:23
  • @ВячеславДмитрюков, это зависит от архитектуры, на которой программа будет использоваться(я имею в виду используемые векторные инструкции). Длина важна потому, что векторные инструкции работают с длинами, кратными 2(не со всеми, разумеется), поэтому надо строку делить на куски, которые можно обрабатывать векторными инструкциями.
    – ixSci
    27 мар 2016 в 17:47

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.