How to get all possible substrings

[Robert Reno]

Hello,

I've been searching for some way to get all possible substrings out of
an input string. I've found information and scripts on suffix trees,
but the examples I found only return an array of suffixes (hence the
name I guess)...that is, substrings from progressively splitting off
an initial letter from the string. Has anyone run across a C++
implementation of perl's String::Splitter function? That's the kind
of functionality that I'm looking for.

Thanks,

Robert

 

[crimaniak]

Hello,

I've been searching for some way to get all possible substrings out of
an input string.

Something like this:

$fullLength=strlen($string);
for($begin=0;$begin<$fullLength;++$begin)
for($l=$fullLength-$begin;$l>0;--$l)
echo substr($string,$begin,$l)."\n";

 

[crimaniak]

Something like this:

$fullLength=strlen($string);
for($begin=0;$begin<$fullLength;++$begin)
 for($l=$fullLength-$begin;$l>0;--$l)
  echo substr($string,$begin,$l)."\n";

Oh, no! I was in PHP conference now and this is result. %-)

 

[tonydee]

Hello,

I've been searching for some way to get all possible substrings out of
an input string.  I've found information and scripts on suffix trees,
but the examples I found only return an array of suffixes (hence the
name I guess)...that is, substrings from progressively splitting off
an initial letter from the string.  Has anyone run across a C++
implementation of perl's String::Splitter function?  That's the kind
of functionality that I'm looking for.

Have a look at boost's tokenize library.

Cheers,
Tony

 

[P. Lepin]

I've been searching for some way to get all possible substrings out of
an input string. I've found information and scripts on suffix trees,
but the examples I found only return an array of suffixes (hence the
name I guess)...that is, substrings from progressively splitting off
an initial letter from the string. Has anyone run across a C++
implementation of perl's String::Splitter function? That's the kind
of functionality that I'm looking for.

I'm not sure I understood you correctly -- is this what you need?

#include <cassert>
#include <algorithm>
#include <vector>
#include <string>

typedef std::vector<std::string> substrVector;
typedef std:air<substrVector, substrVector> substrHelperType;

class Prepend : public std::unary_function<std::string, std::string> {
private: std::string prefix_;
public:
Prepend(const std::string &prefix): prefix_(prefix) {}
std::string operator() (const std::string &str) {
return prefix_ + str;
}
};

substrHelperType substringsHelper(const std::string &str) {
size_t len = str.length();
assert(len > 0);
std::string x(str.begin(), str.begin() + 1);
if (len > 1) {
substrHelperType rest =
substringsHelper(std::string(str.begin() + 1, str.end()));
substrVector p(1, x), np(rest.first);
p.resize(rest.first.size() + 1);
std::transform(rest.first.begin(), rest.first.end(),
p.begin() + 1, Prepend(x));
np.resize(np.size() + rest.second.size());
std::copy(rest.second.begin(), rest.second.end(),
np.end() - rest.second.size());
return substrHelperType(substrVector(p), substrVector(np));
} else {
return substrHelperType(substrVector(1, x), substrVector());
}
}

substrVector substrings(const std::string &str) {
substrHelperType res = substringsHelper(str);
res.first.resize(res.first.size() + res.second.size());
std::copy(res.second.begin(), res.second.end(),
res.first.end() - res.second.size());
return substrVector(res.first);
}