ICPC/Regional/2008G

出展 †

• ICPCアジア地区予選 会津大会 2008 問題文(AOJ)

解法 †

• テキスト位置と，その位置までで使ったパターン集合の組でビットDP
  • DP[t][S] は，t文字目を末尾とするテキストの部分文字列で，Sに属する文字列の順列に一致する物が存在すればtrue
  • 長さliのパターンpiがt文字目を末尾として存在すれば，DP[t][1<<i] = trueで，DP[t-li][S^(1<<i)] = trueならDP[t][S]もtrue

回答 †

• 2008G_pes.cpp - ビットDP(pes)