给出错误的输出：如何将字符串分解为字典单词

Question

我想实现将给定字符串分解为其组成字典单词问题的解决方案，但是我的代码给出了错误的输出，如“icecreamicecream”在输出中得到一些单词两次。请让我知道我出错的地方。以下是我的代码：

#include <set> 
#include <algorithm> 
#include <iostream> 
#include <cstdio> 
#include <cstdlib> 
#include<string.h> 
#define MAX 12 
using namespace std; 
string arr[]={"i", "like", "sam", "sung", "samsung", "mobile", "ice","cream", "icecream", "man", "go", "mango"}; 
set<string> dictionary (arr,arr+MAX); 
int cnt=0; 
void print_words(string str,int i,int j)//i and j denote starting and ending indices respectively of the string to be matched 
{ 
    if(i>j||j>=str.length()||i>=str.length()) 
     { 
     return; 
     } 
    string temp (str, i, j-i+1); 
    if(dictionary.find(temp)==dictionary.end()) 
     print_words(str,i,j+1); 
    else 
    { 
     cout<<temp<<endl; 
     cnt++; 
     print_words(str,j+1,j+1); 
     print_words(str,i,j+1); 
    } 

} 
int main() 
{ 
    string str; 
    cin>>str; 
    print_words(str,0,0); 
    cout<<cnt<<endl; 
    return 0; 
} 

对于字符串icecreamicecream：我想这是输出的顺序：我发现以线性方式的所有单词 我冰淇淋我冰淇淋冰淇淋冰淇淋 1，然后回溯得到剩余的话。

Answer 1

这里是一个解决方案（与不完全输出你想要的）(live example)：

#include <set> 
#include <algorithm> 
#include <iostream> 
#include <cstdio> 
#include <cstdlib> 
#include<string.h> 

using namespace std; 
string arr[]={"i", "like", "sam", "sung", "samsung", "mobile", "ice","cream", "icecream", "man", "go", "mango"}; 
set<string> dictionary (arr,arr+MAX); 
int cnt=0; 

void search_grow(string str, int i, int j) 
{ 
    if(i > j || j >= str.length() || i >= str.length()) 
    { 
     return; 
    } 

    string temp(str, i, j - i + 1); 
    if(dictionary.find(temp) != dictionary.end()) 
    { 
     std::cout << "[search_grow] " << temp << "\n"; 
     cnt++; 
    } 
    search_grow(str, i, j + 1); 
} 

void search_part(string str) 
{ 
    for(int t = 0; t < str.size(); t++) 
     search_grow(str, t, t); 
} 

int main() 
{ 
    string str; 
    cin>>str; 
     search_part(str); 
    cout<<cnt<<endl; 
    return 0; 
} 

理念：做一个线性搜索（search_grow()），通过延长结束要在字典中搜索的字符串，然后开始重复字符串中的每个位置。

输出：

[search_grow] i 
[search_grow] ice 
[search_grow] icecream 
[search_grow] cream 
[search_grow] i 
[search_grow] ice 
[search_grow] icecream 
[search_grow] cream 
8 

Answer 2

也许这样（使用STL和迭代器）？

#include <iostream> 
#include <set> 
#include <vector> 
using namespace std; 

//use a comparison function to define a custom ordering 
//by which to order the strings based on length instead 
//of by character: 
struct CompareStrings { 
    bool operator() (const string& s1, const string& s2) { 
     return s1.size() < s2.size(); 
    } 
}; 

int main() { 
    const char *arr[] = {"i", "like", "sam", "sung", "samsung", "mobile", "ice","cream", "icecream", "man", "go", "mango"}; 
    size_t arr_size = sizeof(arr)/sizeof(arr[0]); 

    //initialize the set with the array and with the custom ordering function: 
    set <string, CompareStrings> dictionary (arr, arr+arr_size); 
    vector <string> solutions; 

    set <string>::iterator it; 
    vector <string>::iterator jt; 

    string test_string = "icecreamicecream"; 

    for (it = dictionary.begin(); it != dictionary.end(); ++it) { 
     size_t found = test_string.find(*it); 

     while (found != string::npos) { 
      if (found != string::npos) { 
       solutions.push_back(*it); 
      } 
      found = test_string.find(*it, found+1); 
     } 
    } 

    //iterate over the solutions: 
    for (jt = solutions.begin(); jt != solutions.end(); ++jt) { 
     cout << *jt << endl; 
    } 

    return 0; 
} 

此输出：

i 
i 
ice 
ice 
cream 
cream 
icecream 
icecream 

注意：输出被命令这样，主要是因为这些值被存储根据其元件首先发现在该组（其本身是由如何sets确定将它们各自的值存储在存储器中）。

更新：

已更新以反映自定义排序功能。

参考：

Sorting a set<string> on the basis of length