給出錯誤的輸出：如何將字符串分解爲字典單詞

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