Теперь Седжвик.
Дано:
Напишите эффективную программу, которая определяет длину самой большой последовательности пробелов в данной строке, просматривая как можно меньшее количество символов.
Подсказка:
С возрастанием длины последовательности пробелов программа должна выполнятся быстрее.
Сам код подсчета пробелов может быть например таким:
#include <iostream>
#include <string>
int count( const std::string& input )
{
int iSpaces = 0;
for (int i = 0; i < input.size(); ++i)
if (input[i] == ' ') ++iSpaces;
return iSpaces;
}
int main()
{
std::string input;
std::cout << "Enter text: ";
std::getline( std::cin, input );
int numSpaces = count( input );
std::cout << "Number of spaces: " << numSpaces << std::endl;
std::cin.ignore();
return 0;
}
То есть, интуиция мне подсказывает, что время выполнения искомой программы не менее чем O(N). Ну сосчитаем мы пробелы, дальше что? Загнать их в структуру данных X и отсортировать? Бред, по-моему...