Как найти самое длинное слово в текстовом документе? - PullRequest
Новая
       7

Как найти самое длинное слово в текстовом документе?

2 голосов
/ 02 января 2011


Я ищу способ найти самое длинное слово (основанное на длине) в текстовом документе, используя STL и повышение. Вот мое решение. Тем не менее, это было не совсем хорошо, было слишком много операций (токен, сортировка ..). Есть ли более простой способ решить эту проблему? 

// utility and memory
#include <utility>
#include <functional>
#include <memory>

#include <locale>
#include <string>

// data structure and algorithm
#include <stack>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <deque>
#include <list>
#include <bitset>
#include <algorithm>
#include <iterator>
// numeric 
#include <complex>
#include <numeric>
#include <valarray>

// input/output
#include <iostream>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <streambuf>
#include <sstream>

// standard C
#include <cctype>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <cstring>

// boost
#include <boost/tokenizer.hpp>

int main() {
    std::string str = "Test, test!, test...string";
    boost::char_separator<char> sep( ",!,.-" );
    boost::tokenizer<boost::char_separator<char> > tokens( str, sep );
    std::vector<std::string> res;
    std::copy( tokens.begin(), tokens.end(), std::back_inserter( res ) );
    std::sort( res.begin(), res.end(), []( const std::string& l, const std::string& r ) { return l.length() > r.length(); } );
    std::cout << "longest : " << *res.begin() << "\n";
    return 0;
}

С уважением,
Чан

Ответы [ 3 ]

3 голосов
/ 02 января 2011

Вы можете использовать std::max_element. Просто дайте ему пару итераторов и компаратор, который вы уже написали.

2 голосов
/ 02 января 2011

Это один способ, и он работает, но есть одна проблема с ним: он работает в O (n lg n), что является сложностью алгоритма сортировки.будет сканировать токены один за другим и отслеживать самое длинное слово на каждом шаге.В конце цикла у вас будет одно из самых длинных слов в наборе.Я сказал один, потому что может быть более одного слова с одинаковой длиной.Таким образом, вы захватите только первое, с чем столкнетесь.

Возможно, вы захотите изменить алгоритм для отслеживания всех самых длинных слов, видимых на каждом этапе.

1 голос
/ 02 января 2011

Вместо того, чтобы хранить и сортировать весь массив токенов слов, вы можете просто найти длину каждого токена и сравнить его с max_length, замеченным до сих пор. Это уменьшит ваши требования к пространству, а также устранит вычислительную сложность сортировки.

...