Разбить строку на слова

Question

Я ищу наиболее эффективный алгоритм для формирования всех возможных комбинаций слов из строки.Например:

Input String: forevercarrot

Output:

forever carrot
forever car rot
for ever carrot
for ever car rot

(все слова должны быть из словаря).

Я могу придумать подход грубой силы.(найти все возможные подстроки и сопоставить), но что может быть лучше?

Answer 1

Используйте дерево префиксов для вашего списка известных слов. Вероятно, библиотеки вроде myspell уже делают это. Попробуйте использовать готовый.

Как только вы нашли совпадение (например, «машина»), разделите ваши вычисления: одна ветвь начинает искать новое слово («гниль»), другая продолжает исследовать варианты текущего начала («морковь»). *

Эффективно, вы поддерживаете пару пар (start_position, current_position) смещений в вашей строке каждый раз, когда вы разделяете вычисления. Несколько потоков могут выскочить из этой очереди параллельно и попытаться продолжить слово, которое начинается с start_position и уже известно до current_position пары, но не заканчивается там. Когда слово найдено, оно сообщается, и другая пара извлекается из очереди. Когда это невозможно, результат не генерируется. Когда происходит разделение, новая пара добавляется в конец очереди. Первоначально очередь содержит (0,0).

Answer 2

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

Как разбить строку на слова.Пример: "stringintowords" -> "Строка в слова"?

Answer 3

Строка ввода: forevercarrot

Выход:

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

программа:

#include<iostream>
#include<string>
#include<vector>
#include<string.h>
void strsplit(std::string str)
{
   int len=0,i,x,y,j,k;
   len = str.size();
   std::string s1,s2,s3,s4,s5,s6,s7;
   char *c = new char[len+1]();
   char *b = new char[len+1]();
   char *d = new char[len+1]();
   for(i =0 ;i< len-1;i++)
   {
       std::cout<<"\n";
       for(j=0;j<=i;j++)
       {
          c[j] = str[j];
          b[j] = str[j];
          s3 += c[j];
          y = j+1;
       }
       for( int h=i+1;h<len;h++){
          s5 += str[h];
       }
       s6 = s3+" "+s5;
       std::cout<<" "<<s6<<"\n";
       s5 = "";
       for(k = y;k<len-1;k++)
       {
          d[k] = str[k];
          s1 += d[k];
          s1 +=  " ";
          for(int l = k+1;l<len;l++){
           b[l] = str[l];
           s2 += b[l];
         }
       s4 = s3+" "+s1+s2;
       s7 = s4;
       std::cout<<" "<<s4<<"\n";
       s3 = "";s4 = "";
       }
       s1 = "";s3 = "";
    }
}

int main(int argc, char* argv[])
{
    std::string str;
    if(argc < 2)
                std::cout<<"Usage: "<<argv[0]<<" <InputString> "<<"\n";
    else{
                str = argv[1];
                strsplit(str);
    }

return 0;
}

Answer 4

Реализация psuedocode, использующая тот факт, что каждая часть строки должна быть словом, мы не можем ничего пропустить.Мы работаем вперед от начала строки до тех пор, пока первый бит не станет словом, а затем генерируем все возможные комбинации остальной части строки.Как только мы это сделаем, мы продолжим, пока не найдем другие возможности для первого слова и т. Д.

allPossibleWords(string s, int startPosition) {
    list ret
    for i in startPosition..s'length
        if isWord(s[startPosition, i])
            ret += s[startPostion, i] * allPossibleWords(s, i)
    return ret    
}

Ошибка в этом коде заключается в том, что в итоге вы будете повторять вычисления -в вашем примере вам придется рассчитать allPossibleWords("carrot") дважды - один раз в ["forever", allPossibleWords["carrot"]] и один раз в ["for", "ever", allPossibleWords["carrot"]].Так что запоминание это то, что нужно учитывать.