algorithm - 将字符串拆分为单词

Question

我正在寻找最有效的算法来从字符串中形成所有可能的单词组合。例如：

Input String: forevercarrot

Output:

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

（所有单词都应该来自字典）。

我可以想到一种蛮力方法。（找到所有可能的子字符串并匹配）但有什么更好的方法？

Answer 1

为您的已知单词列表使用前缀树。可能像myspell已经这样做的库。尝试使用现成的。

一旦找到匹配项（例如“car”），拆分计算：一个分支开始寻找新词（“rot”），另一个分支继续探索当前开头的变体（“carrot”）。

(start_position, current_position)每次拆分计算时，您实际上都会在字符串中维护成对的偏移量队列。几个线程可以并行地从这个队列中弹出，并尝试继续一个从该对开始start_position并且已经知道的单词current_position，但不会在那里结束。当找到一个单词时，它会被报告并从队列中弹出另一对。当不可能时，不会产生任何结果。当分裂发生时，一个新的对被添加到队列的末尾。最初，队列包含一个(0,0).

Answer 2

请参阅这个问题，它有更好的答案。这是一个标准的动态规划问题：

如何将字符串拆分为单词。例如：“stringintowords”->“String Into Words”？

Answer 3

一个伪代码实现，利用字符串的每个部分都必须是一个单词的事实，我们不能跳过任何东西。我们从字符串的开头开始工作，直到第一位是一个单词，然后生成字符串其余部分的所有可能组合。一旦我们这样做了，我们就会继续前进，直到我们找到第一个单词的任何其他可能性，依此类推。

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")两次 - 一次 in["forever", allPossibleWords["carrot"]]和一次 in ["for", "ever", allPossibleWords["carrot"]]。所以记住这一点是需要考虑的。

Answer 4

输入字符串：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;
}