Sed alternative for search and replace on very long lines

I have files that were generated by a program that did not put newlines at the end of records. I want to put newlines between the records, and I can do so with a simple sed script:

sed -e 's/}{/}\n{/g'

The problem is that the input files are multiple gigabytes in size, and therefore the input lines to sed are multiple GBs in length. sed tries to hold a line in memory, which doesn't work in this case. I tried the --unbuffered option, but that just seemed to make it slower and did not allow it to finish correctly.