Anonymous Monk,
I don't know of a module on CPAN that does exactly what you want. Here is how I would do it:

• 1. Index the offset of newlines in the string much like Tie::File does with files
• 2. Perform binary search to find the line that the offset belongs on
• 3. Subtract the newline offset of that line from the given offset to find the offset in that line
• 4. Reset your start newline to the last visited making subsequent binary searches faster