The grep-oriented tools have it a bit easier. They can (and do) extract inner literals as well. The trick is that the search is line oriented and lines tend to

The grep-oriented tools have it a bit easier. They can (and do) extract inner literals as well. The trick is that the search is line oriented and lines tend to be small. So when you find a match for an inner literal, all you need to do is find the bounds of the line that contains the literal and run the full regex engine on just that line. It works extremely well when matches are somewhat rare. As for RE2, backward matching is used to find the starting location of a match.