Sunday, February 24, 2013

backtracking using stack/deque


void GetSentence(string text,vector<string> dictionary)
{
deque<pair<string,int>> my_deque;
hash_set<string> my_hash;
int N=dictionary.size();
vector<int> temp(text.length());
fill(temp.begin(),temp.end(),-1);
for(int i=0;i<N;i++)
my_hash.insert(dictionary[i]);
my_deque.push_back(pair<string,int>::pair("",-1));
while(!my_deque.empty())
{
pair<string,int> top_string=my_deque.back();
int cur_pos=top_string.second;
if(cur_pos==text.length()-1)
break;
bool flag=false;
for(int i=cur_pos+1;i<text.length();i++)
{
string sub_string=text.substr(cur_pos+1,i-cur_pos);
hash_set<string>::iterator iter=my_hash.find(sub_string);
if(iter!=my_hash.end() && i>temp[cur_pos+1])
{
my_deque.push_back(pair<string,int>::pair(sub_string,i));
temp[cur_pos+1]=i;
flag=true;
break;
}
}
if(!flag)
my_deque.pop_back();
}
if(!my_deque.empty())
my_deque.pop_front();
while(!my_deque.empty())
{
pair<string,int> cur_pair=my_deque.front();
my_deque.pop_front();
cout<<cur_pair.first<<" ";
}
cout<<endl;
}

No comments:

Post a Comment