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 = ();
}
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 = ()
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
-
Are you posting in the right place? Check out Where do I post X? to know for sure.
-
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big>
<blockquote> <br /> <dd>
<dl> <dt> <em> <font>
<h1> <h2> <h3> <h4>
<h5> <h6> <hr /> <i>
<li> <nbsp> <ol> <p>
<small> <strike> <strong>
<sub> <sup> <table>
<td> <th> <tr> <tt>
<u> <ul>
-
Snippets of code should be wrapped in
<code> tags not
<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
intervention).
-
Want more info? How to link
or How to display code and escape characters
are good places to start.