Finding distinct substrings

[pranay_agg]

hi, can someone please tell me the approach i should take to find the distinct substrings of a string ?

[VernonDozier]

The question is too vague. Give us an example of a string and the appropriate substrings for that string.

[Ancient Dragon]

Do you mean std::string? Yes, then use its find() method. If you mean character array then use standrd C function strstr() which is declared in string.h (or cstring for c++ programs)

Of course you may not be allowed to use either of those if your instructor wants you to write your own function.

[pranay_agg]

The question is too vague. Give us an example of a string and the appropriate substrings for that string.

e.g 1
string s = "ccccc"
then ans = 1
e.g 2
s = "abc"
ans = 7

[VernonDozier]

e.g 1
string s = "ccccc"
then ans = 1
e.g 2
s = "abc"
ans = 7

Not sure what you mean. 2 and 7 aren't substrings and they aren't the number of distinct substrings either. I can make more than two substrings from "ccccc". ("c", "cc", "ccc", "cccc"). You're going to have to explain what you are doing and how you got those answers.

[pranay_agg]

Not sure what you mean. 2 and 7 aren't substrings and they aren't the number of distinct substrings either. I can make more than two substrings from "ccccc". ("c", "cc", "ccc", "cccc"). You're going to have to explain what you are doing and how you got those answers.

sorry it was a mistake
for s = ccccc
no of distinct substrings are 5
and for s = ababa
its 9

[pranay_agg]

Not sure what you mean. 2 and 7 aren't substrings and they aren't the number of distinct substrings either. I can make more than two substrings from "ccccc". ("c", "cc", "ccc", "cccc"). You're going to have to explain what you are doing and how you got those answers.

sorry it was a mistake
for s = ccccc
no of distinct substrings are 5
and for s = ababa
its 9

[VernonDozier]

So are you looking for an algorithm, looking for code, what? The brute force way would be to set up a vector (or whatever storage you want to use) and generate all substrings one by one. Search the vector (Binary Tree might be better) and if the substring is already there, don't insert. If it isn't there, insert. At the end, you have a tree/vector/whatever of all the substrings.

That's a brute force way. There may be more elegant/efficient methods.

[tetron]

you would want two methods:

1st method get all of the sub strings of a length for each input

2nd method find the unique strings of a length

#include <vector>
#include <string>

class sub_string_counter()
{
public:
sub_string_counter();
std::vector<std::string> get_substrs(std::string & from,  int len);
int unique_strings(std::vector<std::string> &vs);
}

the function you need for 1 is .substr() you need the start and length parameters

//pseudo code
std::string input;
//do while start + length <= input.size();
std::string output = input.sub_str(start, length);
vs.push_back(output);

the next stage requires that you find the unique values in the vector

you can test the current string against all of the strings before it in the vector if not found
increase count
else
do nothing

sorry it was a mistake
for s = ccccc
no of distinct substrings are 5
and for s = ababa
its 9

[Ancient Dragon]

<deleted>

[mrnutty]

If you don't need to print out the actual permutations, then you can
just calculate the number of different permutation.
Maybe something like this would work :

return  pow(2.0 , double( strlen(str) ) ) - 1;

[Ancient Dragon]

If you don't need to print out the actual permutations, then you can
just calculate the number of different permutation.
Maybe something like this would work :

return  pow(2.0 , double( strlen(str) ) ) - 1;

I don't think so. In "ccccc" there are only 5, but your formula would product (2^5)-1 = 31.

[mrnutty]

I don't think so. In "ccccc" there are only 5, but your formula would product (2^5)-1 = 31.

Oh, wait, should have read the title, he needs only the distinct ones.
I'll try to formulate something.