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