Saturday, March 1, 2014

Find all unique substrings of a string

/*
 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