そんなにおおげさにしなくてもいいのかもしれない。

保存する必要があるのは、「マッチした位置と長さ」と「次の一文字」だけでいいのかもしれない。で、

1. 次の一文字を読み込み、それを保存する。次のマッチを試す。次のマッチが前のマッチより短いか、またはマッチしなければ2へ。そうでなければ3へ

2. 一文字読み込みずみなので、前に「マッチした位置と長さ」を出力し、マッチの長さから1減算した文字数だけ読み捨てる。

3. 保存した前に「マッチした位置と長さ」は捨てる。保存した「次の一文字」を出力し新たに「マッチした位置と長さ」を出力し、マッチの長さの文字数だけ読み捨てる。

こんな感じかな。