srik4u,
the solution I was given in a recent post of mine, find all paths of length n in a graph, might offer a good place to start. Using the idea of a trie, you could recursively build the phrases as you go along. I am not good at writing recursive functions, but the idea is basically this: recursively iterate over the string and pop off substrings that match whole words. The phrase fails when you have a substring that is not a partial word. You have a valid phrase when you have reached the end of the string without failing on a substring. A function might look something like this:

sub check_string($word) {
    foreach $chr (split //, $word) {
        $check .= $chr;
        if whole_word($check) {
            push @phrase, $check;
            $rem = substr($word, length($check), length($word) - lengt
+h($check));
            check_string($remainder);
        } elsif not_valid($check) {
            @phrase = ();
            return;
        }
    }

        print "@phrase\n";
        @phrase = ();
}
[download]

as I say I am not good at recursive functions, so the above is merely a starting place. (getting the recursive element to work always befuddles me). More visually, this is what would happen with the string "mycarrot"

m    valid partial string, so continue
my   found a whole word, so push and recurse
     @phrase = ("my")

c    valid partial string, so continue
ca   valid partial string, so continue
car  found a whole word, so push and recurse
     @phrase = ("my", "car")

r    valid partial string, so continue
ro   valid partial string, so continue
rot  found a whole word, so push
     at end of string, so print valid phrase
     @phrase = ("my", "car", "rot")
     

(backup to last iteration and continue)
    @phrase = ("my")

carr   valid partial string, so continue
carro  valid partial string, so continue
carrot found a whole so push
       at end of string, so print valid phrase
       ("my", "carrot")

back to last iteration and continue)
       @phrase = ()

myc   invalid partial string, so quit
      @phrase = ()
[download]

In the scary place I call my mind, this makes sense. I hope it makes sense to you. Maybe if someone else understands what I am trying to explain, they might be able to clarify it better than I.

davidj

---

---

Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!

Titles consisting of a single word are discouraged, and in most cases are disallowed outright.

Read Where should I post X? if you're not absolutely sure you're posting in the right place.

Please read these before you post! —

• How do I compose an effective node title?
• How do I post a question effectively?
• Markup in the Monastery

Posts may use any of the Perl Monks Approved HTML tags:

a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr

You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)

	For:		Use:
	&		&
	<		&lt;
	>		&gt;
	[		&#91;
	]		&#93;

Link using PerlMonks shortcuts! What shortcuts can I use for linking?

See Writeup Formatting Tips and other pages linked from there for more info.