this is in no way embarrassingly parallel at all! in fact, it's entirely non trivial to parallelise, writing the output is an inhertintly a serial operation.
Could you not do something like chunk the input and operate on the pieces in parallel? I'd think you could use something like a rope (à la text editors) to support the concurrent writes.
(I may or may not have forgotten the differences between concurrency and parallelism.)
yeah, you could split the input into chunks, but then you're left with the problem of recombining the outputs from each portion into one string - that operation must be serial and would likely outweigh the benefits of the initial parallelism in most cases.