/*
copyright: Puneet Sohi
*/
#include <iostream>
#include <string>
#include <vector>
#include <tr1/unordered_map>
using namespace std;
using namespace tr1;
vector<string> findSubStr(string s){
//find all unique substr of s. Hashmap used
//to filter out the duplicates
vector<string> v (1);
vector<string> v1 (1);
char c;
int i=0;
string s1, t;
string subS;
unordered_map<string, int>m;
if(s.length() <= 1){
c = s[0];
s1.append(1, c);
v[0] = s1;
return v;
}
c = s[0];
s1.append(1,c);
v[0] = s1;
m[s1] = 1;
subS = s.substr(1, s.length()-1);
v1 = findSubStr(subS);
for(i=0; i < v1.size(); i++){
t = v1[i];
if(m[t] == 0){
v.push_back(t);
m[t] = 1;
}
t = s1 + t;
if(m[t] == 0){
v.push_back(t);
m[t] = 1;
}
}
return v;
}
int main () {
int i = 0;
string s1 = "aa";
vector<string> v (1);
v = findSubStr(s1);
while(i<v.size()){
cout << v[i] << endl;
i++;
}
return 0;
}
No comments:
Post a Comment