Kohei Morita

自分としては{a, aa, aaa, ...}も入れるのを推しておきます(aho-corasickでもこれ入ってても線形で解ける気がしたからなんですが、解けないかもしれません(ええ…))

Suffix Arrayでどうにかならない問題を考えるのはしんどいと思います　Suffix Array + LCP + Sparse Tableセットは(実装量にさえ目をつぶれば)とにかく汎用性が高いので　Suffix Automaton"でも"解ける問題を用意する方が現実的？ T_iでAho-Corasickを作ったあと、各ノードを訪れた回数を列挙して、それをSuffix Link上でDP(というか累積和)すれば回数が数えられる気がしてます(もちろん出現回数のsumはO(N^1.5))

Aho-Corasickをverifyするめちゃくちゃ直接的な案として、Aho-Corasickを直接出力させるという案があります(https://github.com/yosupo06/library-checker-problems/issues/175 ) これをSuffix Arrayにも適用できるかも Suffix Automatonはそもそも定義が一意なのかすらよくわかってない

Suffix Automatonについて、実は部分文字列を全部受理する頂点数が線形のautomaton しか知らないです　ですがその定義なら一意に定まりそうで良さそう

案1よさそうです, `ans(a, b, m, L, R) = ans(a, aL + b, m, 0, R-L)`ですか？だったらさすがにL = 0でいい気がします。 案2は答えが一意じゃないような気がしていて、ちゃんとcheckerがかけるのかすらよくわかっていません

提案ありがとうございます！ 正直計算量O(E * dijkstra)なら、ダイクストラ法のちょっとした応用という印象で、入れなくてもいいのかなと感じました 関連として、最短平均長さ閉路なら入れたい気がします (ref http://lemon.cs.elte.hu/pub/doc/1.2.3/a00536.html#:~:text=The%20minimum%20mean%20cycle%20problem,number%20of%20arcs%20on%20it.&text=results%20in%20a%20conservative%20length%20function.)

確かに書いてなかったですね　やば(checker.cppからparams.hをインクルード出来るべきではという話はある)

そもそもpermutation treeの厳密な定義がわからなかったので学習しています　現状以下のような理解なのですが、間違っていたら指摘していただけるとありがたいです。 --- 順列の要素の部分集合について、(非空 & 連続 & max - min = R - L)なものの性質について考えている。permutation treeとはこれらからなる集合族(部分集合の集合)を表す木表現。 permutation treeの各ノードは3つの要素を持つ - node type: cut or join - Fの要素W - (そのノードの表す)Fの部分集合Q ここで、Wに注目するといい感じの木表現になっている。つまり、 -...

オンラインクエリ版もって無いのでどのぐらいの定数倍なのか不明

クエリ2を行うと要素数が2倍に増えるはずで、なので2^{500000}ぐらいのサイズのheapが出来て、するとO(log 要素数) = 500000ぐらいになって、計算量が破滅する気がします