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.

Your problem has several solutions, but you do not seem to separate them (example solutions: `ice cream ice cream`, `icecream icecream`, `i cream icecream`...). — Synxis, Feb 08 '14 at 17:31
According to me the output displayed should be: i ice cream i ice cream icecream icecream — amiageek, Feb 08 '14 at 17:33
You should post what you expect/want in the question (with more details than in your comment). — Synxis, Feb 08 '14 at 17:38
Ok, but: this is not a linear search (before the "backtracking"). With a linear search, you will get `i cream` (notice that the `ice` is not present). — Synxis, Feb 08 '14 at 17:43

score 0 · Answer 1 · edited May 23 '17 at 12:20

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

score 0 · Accepted Answer · answered Feb 08 '14 at 18:02

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

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

2 Answers2