Giving wrong output: How to break a string into dictionary words

Question

I am trying to implement the solution of breaking a given string into its constituent dictionary words problem, but my code is giving wrong output for strings like "icecreamicecream" wherein I am getting some words twice in the output. Please let me know where I am going wrong. Following is my code:

#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;
}

For the string icecreamicecream: I want this to be the order of the output: i ice cream i ice cream icecream icecream 1st i am finding all words in linear fashion, then backtracking to get the remaining words.

Answer 1

Here is a solution (with not exactly the output you want) (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;
}

Idea: do a linear search (search_grow()), by extending at end the string to search in the dictionary, then starting repeating for each position in the string.

Output:

[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

Perhaps like this (using the STL and iterators)?

#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;
}

This outputs:

i
i
ice
ice
cream
cream
icecream
icecream

Note: that the output is ordered this way mainly because the values are stored depending on which element is found first in the set (which itself is determined by how sets store their respective values in memory).

UPDATE:

Updated to reflect a custom ordering function.

REFERENCES:

Sorting a set<string> on the basis of length