MiddleКодИногдаЕщё не отвечали
Реализуйте fuzzysearch: является ли needle подпоследовательностью haystack?
Реализуйте fuzzysearch(needle, haystack) как нечёткий поиск в редакторе кода: верните true, если needle — подпоследовательность haystack (его символы идут по порядку, не обязательно подряд). Напр. fuzzysearch("cwhl", "cartwheel") — true, fuzzysearch("lw", "cartwheel") — false.
Требования:
- Один проход, без рекурсии. O(|haystack|).
bool fuzzysearch(const std::string& needle, const std::string& haystack) {
// ваш код здесь
}Допишите реализацию.
Два указателя. Идите по haystack; когда символ haystack равен текущему символу needle, двигайте указатель needle. Needle — подпоследовательность тогда и только тогда, когда его указатель дошёл до конца. Один линейный проход, O(|haystack|), константа памяти.
- ✗Путать подпоследовательность (порядок сохранён, пропуски можно) с подстрокой (подряд)
- ✗Проверять лишь наличие символов и игнорировать относительный порядок
- ✗Двигать указатель needle на каждом символе haystack, а не только при совпадении
- →Какие уточняющие вопросы важны (пустой needle, регистр)?
- →Почему жадный однопроходный матч никогда не пропускает валидную подпоследовательность?
Оглавление
Задача
Проверьте, является ли needle подпоследовательностью haystack, за один проход без рекурсии.
Решение
#include <string>
bool fuzzysearch(const std::string& needle, const std::string& haystack) {
size_t n = 0;
for (char c : haystack) {
if (n < needle.size() && c == needle[n]) ++n;
if (n == needle.size()) return true;
}
return n == needle.size();
}Ключевые моменты
- Указатель needle растёт лишь при совпадении; haystack — всегда.
- Подпоследовательность, а не подстрока: пропуски разрешены, порядок — нет.
- Один проход, O(|haystack|), константа памяти.
Оглавление
