逆向き検索って、最後まで検索して、
それで最後に見つかったところを返せばいいんだっしょ。
最後に移動する時に終端を見つけるためにどうせ一度最後まで走査するんだし、
BM 法で検索していけばそれで十分かと。