Support counting strings using regex - Githubissues

kmyk-jikka / Jikka

an automated solver for problems of competitive programming

https://kmyk-jikka.github.io/Jikka/playground

Apache License 2.0

152 stars 11 forks source link

Support counting strings using regex #194

Open kmyk opened 2 years ago

kmyk commented 2 years ago

Description / 説明

「文字列 s の部分文字列であって正規言語 L に含まれるものの数」とか「長さ k 未満の文字列 s ∈ Σ˂ᵏ であって正規言語 L に含まれるものの数」とかは全部まとめて処理できる。普通に正規表現の構文解析して DFA に落とすのをやるだけ

先に https://github.com/kmyk/Jikka/issues/182 が必要
正規表現パートの C++ 実装は完全なものをもう持ってる https://github.com/kmyk/tinydfa
例題: https://judge.kimiyuki.net/problem/count-subsequnce-regex

Motivation / 動機

ないよりはあった方がいいかなって

他の最適化と組み合わさっていい感じになるということが見込めないかなりピンポイントな最適化なので、後回しでいい気がする