Match Maker (UVa Live Archive Africa and the Middle East - Africa and Arab - 2008/2009 Alexandria - Egypt)

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4363

問題

#と*と数値からなるパターンが存在する。#は奇数個、*は偶数個の任意の数値とみなせる。
パターンと数値が与えられるので数値がパターンにマッチするか判定せよ。
パターンの長さ、数値の長さ<=100000

解法

calc(left, right)という関数を作る。calc(left, right)はパターンがleft番目の文字まで、数値がright番目の文字までマッチした状態で全体のマッチが成功するなら1、次の#,*までマッチはできたが全体はマッチできなかったら-1、それ以外の場合は0を返す関数。
こうしておくと#,*でマッチさせるときに次の再帰呼び出しが1を返せば成功、-1を返すと失敗となり、0を返したら#,*で消費する数値の個数を増やしてもう一度試すということを繰り返せば良い。次の#,*まで来たときにrightは最小の値になっているはずなのでこれで正しい結果が帰ってくる。(それよりも大きい値はその#,*で自由に作れるので)
数値の長さをnとすると全体のオーダーは最悪のケースでO(n^2)になるが#,*が一定間隔cで存在すればO(nc)で実行可能になる。