https://twitter.com/kinaba のログ (twilog の方が便利です。)
| @sinya8282 昔のツイートが流れていたので突然の亀レスですがThompson的なのはNFAサイズe文字列サイズnでΘ(en)なので両方同時に入力とすると線形に収まらぬのでは。(知る限り線形に収まるのは結構限定されたクラス http://www.grappa.univ-lille3.fr/~staworko/papers/groz-pods12.pdf | |
| Easyで証明してないgreedyをガンガン倒していく傾向があるのは喜ばしいのだけどgreedy以外の解法が難しすぎませんこと… |