本日はヴィルト先生のアルゴリズム本を読む。

正規表現、正規言語を習得中。ある程度マッチングが進んだあとでマッチングに失敗したことが確定した場合、効率よくトラックバックするにはどうしたらよいのか。「.*」ではじまるマッチングをかける場合、１回失敗したあとに２桁目に移動するのは無意味である。２回目以降は、かならず失敗することは明白である。それ以外のケースでは効率の良いトラックバックはあるのか。現実的には、「.*」のような極端なパターンを例外として随時１文字づつシフトさせるのが良いのか。探索アルゴリズムでそんなものがあったような気がしてヴィルト先生の本を読むが、ステートマシンに応用できそうなものはなさそう。