How to get all possible substrings

Discussion in 'C++' started by Robert Reno, Jan 26, 2010.

  1. Robert Reno

    Robert Reno Guest

    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
    Robert Reno, Jan 26, 2010
    #1
    1. Advertising

  2. Robert Reno

    Guest

    On 26 Ñнв, 03:14, Robert Reno <> wrote:
    > 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";
    , Jan 26, 2010
    #2
    1. Advertising

  3. Robert Reno

    Guest

    On 26 Ñнв, 11:04, ""
    <> wrote:
    > 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. %-)
    , Jan 26, 2010
    #3
  4. Robert Reno

    tonydee Guest

    On Jan 26, 9:14 am, Robert Reno <> wrote:
    > 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
    tonydee, Jan 26, 2010
    #4
  5. Robert Reno

    P. Lepin Guest

    Robert Reno wrote:
    > 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::pair<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);
    }

    --
    P. Lepin
    P. Lepin, Jan 28, 2010
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Markus
    Replies:
    1
    Views:
    457
    Markus
    Nov 22, 2005
  2. Replies:
    8
    Views:
    641
    Thorsten Kampe
    Jul 13, 2006
  3. shapper

    Get Substrings

    shapper, Apr 30, 2007, in forum: ASP .Net
    Replies:
    2
    Views:
    344
    Mark Rae
    Apr 30, 2007
  4. kadau
    Replies:
    3
    Views:
    95
    Brian McCauley
    Mar 25, 2005
  5. puzzlecracker

    enumerate all adjecent substrings in the file

    puzzlecracker, Dec 11, 2005, in forum: Perl Misc
    Replies:
    9
    Views:
    121
    Anno Siegel
    Dec 13, 2005
Loading...

Share This Page