If, as it would seem, the definition of this problem looks-at the string as a concatenation of interesting-values ... such as prefixes and suffixes of an English word ... then perhaps what you really need here is “a hash of hashes.”

In other words, if your problem looks at the string “prefoobar” as “pre+foobar,” then the first-level hash (containing “pre”) refers-to a subsequent hash that contains “foobar.”)

If, on the other hand, it looks at the string as a string of n characters where the-important-thing is “what is the probability of character x occurring right-here,” perhaps what you need is a nested set of hashes per-character.

At each position in the tree, you would store (for each character):

1. The probability of “this character”
2. A reference to a hash of possible “next characters” each one similarly (recursively...) described.

In an application like this, your choice of “appropriate data-structure” will be paramount. Make very sure that your chosen data-structure works hard for you. Your data structure should not merely be “a passive-something that other parts of the program can conveniently (and repetitively...) search.” It must be a tool that the program can leverage to efficiently produce the solution.

“Strange” or “awkward” as such-a-structure may feel as you are writing it ... it's the runtime-performance that really matters here. Given the right data-representation (and Perl Is No Slouch!), performance should be “impressive.” (If it isn't, look harder.) Perl is an industrial-strength power tool that eats requirements like this one for lunch...