ちょっと口を挟んでみます
間違いとかあればご容赦を、

▼ げんたさん
> そこで思ったのですが，正規表現を反転？して正規表現エンジンにもreverse_iteratorを与えられるようにしたら真の逆方向検索ができるのではないかと．
正規表現を反転って m/A[a-z]\w+\s/ (適当)を m/\s\w+[a-z]A/ にしちゃってって話ですか?
もしそのことでしたら後方参照や拡張正規表現で泣きますよ^^;

reverse_iteratorってSTLはよく分かりませんが
for(int i=p長さ; i>=0; i--){p[i] で何かする}
ってな感じのものですよね?
これもバッファ先頭/末やCRLFでごちゃごちゃするかと思います

# 否定してばかりですいません、一度試しに組んでみます