Алгоритм для поиска одной десятой самой длинной последовательности пробелов в заданной строке

Question

Ищете алгоритм для поиска длины самой длинной последовательности пробелов в заданной строке, рассматривая как можно больше символов?

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

Я знаю, что решение, которое O (п) .. Но ищу более оптимальное решение

Answer 1

Но в худшем случае (если все символы являются пустыми), вы должны изучить каждый символ. Поэтому он не может быть лучше, чем O (n) по сложности.

Обоснование: предположим, что вся строка пуста, вы не изучили N символов и выходы ваших алгоритмов n. Тогда, если какой-либо незанятый символ не пуст, ваш ответ будет неправильным. Поэтому для этого конкретного ввода вам нужно изучить всю строку.

Answer 2

Вы не сможете найти решение, которое является меньшей сложностью, чем O (n), поскольку вам необходимо пройти через каждый символ в худшем случае со строкой ввода, которая содержит не более 0 или 1 последовательных пробелов, или полностью пробелы.

Вы можете сделать некоторые оптимизации, хотя это все равно будет считаться O (n).

Например:

Пусть М текущий самый длинный матч до сих пор, как вы идете через ваш список. Также предположим, что вы можете получить доступ к элементам ввода в O (1), например, у вас есть массив в качестве входных данных.

Когда вы видите пробелы без пробелов, вы можете пропустить M элементов, если current + M не является пробелом. Разумеется, внутри не может быть пробелов, превышающих M.

И когда вы видите символ белого цвета, если current + M-1 не является пробелом, вы знаете, что у вас нет самых длинных прогонов, вы также можете пропустить в этом случае.

Answer 3

Что бы вы ни делали, наихудший случай всегда будет o (n) - если эти пробелы находятся на последней части строки ... (или последняя «проверенная» часть строки).

Answer 4

Очевидная идея: вы можете прыгать через K + 1 места (где K - это самая длинная временная последовательность) и отсканировать назад, если вы нашли пробел.

Таким образом, у вас есть что-то о (n + n/M)/2 = n (M + 1)/2M позициях.

Редактировать:
Еще одна идея - применить двоичный поиск. Это выглядит следующим образом: для заданного k вы делаете процедуру, которая проверяет, существует ли последовательность пробелов с длиной length> = k. Это может быть достигнуто в шагах O (n/k). Затем вы пытаетесь найти максимальный k с бинарным поиском.

Edit:
В последующих поисках, вы можете использовать знание о том, что последовательность некоторой длиной к уже существует, и начинает пропускать в K с самого начала.

Answer 5

В худшем случае нет возможности сделать это быстрее, чем O(N). Однако, вот несколько оптимизаций, предполагающих индексацию на основе 0.

1. Если у вас уже есть полная последовательность L заготовок (по полной, я имею в виду последовательность, которая не подпоследовательность более крупной последовательности), и L, по меньшей мере, как большой, как половина размера вашей строки, вы может остановиться.
2. Если у вас есть полная последовательность заготовок L, как только вы нажмете пробел в позиции i, проверьте, является ли символ в позиции i + L также пространством. Если это так, продолжайте сканирование с позиции i вперед, поскольку вы можете найти более крупную последовательность - однако, если вы столкнулись с пробелом до позиции i + L, вы можете перейти непосредственно к i + L + 1. Если это не пространство, вы не можете построить большую последовательность, начиная с i, поэтому сканирование начинается с i + L + 1.
3. Если у вас есть полная последовательность заготовок длиной L, и вы находитесь в положении i и у вас есть k позиции слева изучить и k <= L, вы можете остановить поиск, так как очевидно, нет никакого способа, вы будете в состоянии найти что-нибудь лучше.

Чтобы доказать, что вы не можете сделать это быстрее, чем O(N), рассмотрите строку, которая не содержит пробелов. Вам нужно будет получить доступ к каждому символу один раз, так что это O(N). То же самое со строкой, которая содержит только пробелы.