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

Question

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

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

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

Answer 1

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

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

Например:

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

Когда вы видите не пропуски, вы можете пропустить M элементов, если current + M не пропуски. Конечно, внутри не должно быть пробелов длиннее, чем М.

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

Answer 2

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

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

Answer 3

Нет способа сделать это быстрее, чем 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). То же самое со строкой, которая содержит только пробелы.

Answer 4

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

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

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

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

Answer 5

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