library-checker-problems
library-checker-problems copied to clipboard
yosupo06
[問題案] Number of Occurrences(string)
(任意) 問題ID: number_of_occurrences 問題名: Number of Occurrences
問題概要
Hello, 文字列Sが与えられてQ個の文字列T_iが与えられるのでS上でのT_iの出現回数a_iを数えて
入力
S
Q
T_1
:
T_Q
出力
a_1
:
a_Q
制約
|S|, Q, Σ|T_i| <= 5e5
自分としては{a, aa, aaa, ...}も入れるのを推しておきます(aho-corasickでもこれ入ってても線形で解ける気がしたからなんですが、解けないかもしれません(ええ…))
Aho-Corasickは出現位置全部メモったら総長さをNとして最悪O(N^1.5)だよ、この場合{T_i}でAho-Corasick Automaton構築すると思うけど5e5だと間に合わなく内科
ちなみにSuffix Tree/Suffix Automatonをverifyしたいというモチベーションなんだけど大抵の問題Suffix Arrayでどうにかなってしまって困っています、今（まあnumber of substringsとこれバグってなかったら大丈夫やろという精神、offlineクエリでk番目の出現位置を答えるとかにするとSuffix Arrayきついかな、とはいえSuffix Treeでもつらいんですが（更にHLとか載せないと厳しい気がする
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はそもそも定義が一意なのかすらよくわかってない
あたまが よろしいね
あーAho-Corasick直接出力する案あるの ならSuffix TreeとかSuffix Automatonもできるかもな ノードに持たせる情報とか無視すると、両方とも一意だと思うな 特に後者に関しては「部分文字列全体からなるAutomatonを『endposが同一』を同値条件として割ったもの」という定義です
Suffix Automatonについて、実は部分文字列を全部受理する頂点数が線形のautomaton しか知らないです ですがその定義なら一意に定まりそうで良さそう
1年前のOpenCupに、「DAGが与えられるのでこれが文字列sのSuffix Automaton(ここでは頂点数最小と書かれている)になるようなsの辞書順最小のものを求めよ」という問題があって、結局誰も解けてないしこどふぉの議論にすら上がってなかった。 "abb"という文字列をよく紹介されているようなSuffix Automatonの作り方でつくるとsplitが発生して5頂点になるけど、splitしないでも別にいけて4頂点になるから、じゃあ最小のものってどうやって作るんだってなって終わったなーというのを思い出した。 https://official.contest.yandex.ru/opencupXIX/contest/12646/problems/G/
Hi Sorry, I'm not sure whether I got the discussion correctly from the Google Translate.
I just noticed that suffix automaton was discussed here. In general, minimal DFA is unique up to the isomorphism for any regular language. It is also possible to check whether the given, not necessarily minimal, DFA accepts the same language as suffix automaton in linear time (problem O in https://codeforces.com/gym/100133). Is that what was discussed here?
