Suffix Automatonでもやもやした部分をなんか書いただけ
Suffix Automaton
Suffix Automatonを学ぼうとしてたらよくわからない部分があったので適当に書きます
https://cp-algorithms.com/string/suffix-automaton.html
を見たのでだいたいそこを読めばいいと思います
これ書きながら読み直したら全部ちゃんと書いてました(ア)
既にわかっているひとは何が言いたいかわかるかも、まあわかんないよね、ぐらいの気持ちで書いています
僕は自分の知識を共有して周りを強くしようという意志が殆どなく、そもそも誰かに読んでもらう気持ちで書いてないので(ア)
ですます調とかゴッチャゴチャなのも何も気にしていないからです
一度このデータ消えたので適当になりました
消えるまでは小学生が読んでもわかるとてもわかりやすい文章でできた記事だったのに...
Suffix Automatonってなに？
文字列のsuffixを受理するほにゃららオートマトン、受理状態を気にしなければ全部分文字列に対応する状態がある
それぞれの状態(頂点)からは次の文字に応じた状態への遷移があって、なかった場合は今見てる文字列の先頭を削るsuffix linkをたどる
とりあえず、上のURLでも導入されてるendposを導入します
として、一応
みたいなのも
例
S = "abcabcab"
endpos("abcabcab") = endpos("bcabcab") = endpos("cabcab") = {7}
endpos("abcab") = endpos("bcab") = endpos("cab") = {4, 7}
endpos("ab") = endpos("b") = {1, 4, 7}endpos("abcabc") = endpos("bcabc") = endpos("cabc") = {5}
endpos("abc") = endpos("bc") = endpos("c") = {2, 5}
これらの例で、どういうものかは分かると思います(適当)
また、定義とか、この例を見ると がわかります
ある文字列T'が現れる時、そのsuffixは必ずそこに現れるのでまず右が成り立ちます
逆に、出現位置の終端が等しいとすると後ろの方の文字が等しいことがわかり、包含関係にあるときサイズが小さい方が長いこともわかります(長い文字列のほうが短い文字列より出てきにくいからね)
どちらかがどちらかのsuffixであるとき、endposは必ず包含関係になることは少し考えると多分わかります
ここで、Suffix Automatonの状態はendposが等しい部分文字列の集合になっています
suffix linkは自分のsuffixで最も長いものにつけますが、先頭一文字削ったやつとかは同じ状態に入っていることもあるので
異なる状態に入る中で最も長いものにつけます
ちなみに、同じ状態に入っている文字列集合は一番長い文字列 T と一番短い文字列を T'見つけた時、Suf(T) の中で T' よりも長い文字列全てになります。
例を見るとわかると思います
Suffix Automaton の構築
構築部分で、いくつかなんかよくわからないね(考えてないので)みたいなところがありました
まあCorrectnessってところをちゃんと読みましょうなんですけど
一応次に構築方法の手順を書きます(URLのやつをわかりにくくしただけ)
まず各状態は文字ごとの遷移先(next[c])、suffix link(link)、長さ(len)を持ちます
構築方法としては、文字列の先頭から1文字ずつ追加していく感じなので現時点での文字列全体の状態(last)も持ちます
オートマトンなので、最初は初期状態(頂点0)だけを用意しておき、初期状態のlinkは-1にしておくといいらしいです
curとして状態を追加し、cur.len = last.len + 1とします。また、追加する文字をcとしておきます(残りの決める必要があるものはlink)p = lastとして、次の処理を繰り返しますp == -1であるとき、またはp.next[c]が存在するなら繰り返しを抜けますp.next[c] = curとしますp = p.linkとします
- ここで、
p == -1であればcur.link = 0として終了します q = p.next[c]とします- もし
p.len + 1 == q.lenであればcur.link = qとして終了します cloneとしてqをコピーした後、clone.len = p.len+1、cur.link = q.link = cloneとしますpからはじめて、p.next[c] == qである間はp.next[c] = cloneとしてlinkをたどることを繰り返します- 最後に
last = curとして終了です
ここで、次のいくつかがよくわからなくなりました(頭がないので)
- なんで
p.next[c] = curとしながらlinkをさかのぼっていっていいの？ - なんで
p.len + 1 == q.lenだったら放置して終了して大丈夫なの？ - なんで
cloneが必要なの？ - なんで
cloneにnextを張り替えるのはp.next[c] == qである間だけでいいの？それともある場所以降は全部qなの？
とりあえずこれらを僕が解消しようと試みるだけのアです
一応、S = "abcbcc"に対してSuffix Automatonを構築する図を貼っておきます。
suffix linkを図示するの忘れてたけど見にくくなってしまうからということで...
そもそもそこまで説明に使わないし..
オートマトンの成長観察日記です。
頂点の数字はそこに属する文字列の中で最長のものの長さを示しています。
なんでp.next[c] = curとながらlinkをさかのぼっていっていいの？
現時点の文字列がSで、そこにcを付け足してS+cのSuffix Automatonを作ろうとしていると考えます
すると、Suf(S)は初期状態になるまでlinkをたどって状態に属する部分文字列を集めると出来上がる。(Suffix Linkをたどると最長のSuffixの状態に移動するので)
なのでそれらの状態からのcによる遷移をcurに送るとcurで全てのsuffixを受け持つことになる
全てのsuffixがcurにあるので、suffix linkは頂点0に当然向かう
ここで、文字列SによるSuffix Automatonは正しく構築されていることを仮定するので2つの状態に同じ文字列が属していることはない
ちなみに、後で議論するp.len + 1とq.lenの関係について、p.len + 1 < q.lenとなる遷移はここでのみ追加される
なんでp.len + 1 == q.lenだったら放置して終了して大丈夫なの？
ここでも同様にS+cの考え方をしてみます
p.len + 1 == q.lenであるということはqが文字を追加するときにできた状態か、cloneの状態である可能性があります
したがって、pのsuffixにcを追加した文字列の状態は全てqを追加した際に解決されているのでこれ以上さかのぼる必要はありません
また、S+cのsuffixのうちpより長いものはcurに属しているのでcurからのsuffix linkはqで大丈夫です
なんでcloneが必要なの？
cloneを追加するときはp.len + 1 < q.lenであるが、これはqに属する文字列のうちp.len + 1以下のものだけがほしいのにそれより長いものも取ってしまっていることを意味している
ここで、p.len + 1 < |T| <= q.lenだけqに残し、cloneに(qに属するやつで最小の長さ) <= |T| <= p.len + 1となるものが属するようにしたい
ひとまず、qとcloneの関係だけ考えるとcloneはqのsuffixなので、suffix linkはqからcloneに向けてつなげる
cloneのsuffix linkについてはqからもともとつながっていた状態がcloneのより短いものではもっとも長いのでcloneからつなげる
結論としては、qだけだとpにcを追加するときにはqよりもたくさん登場してる状態になっているからcloneで分ける必要がある
最初追加したときには、pからのcによる遷移はqのsuffixに完全に属しているのでのでendposがいい感じになっている
例えば上の観察日記の3日目と4日目を比べると、3日目で主鎖の2と書かれているところには"ab"と"b"が属していてどちらもendpos = {1}である
ただ、4日目になると"b"のendpos = {1, 3}となり"ab"よりも多く登場するので分けなきゃいけない気持ちになる
そういうことです、多分(微妙になんかモヤモヤがあるけど多分無視できるレベルなので無視)
なんでcloneにnextを張り替えるのはp.next[c] == qである間だけでいいの？それともある場所以降は全部qなの？
ある場所以降は全部qなの？ → そんなことはないです、多分
途中からsuffixが一致するようなものを考えるとなんか全部一緒にならないものもあると思うので(曖昧)
ただ、そうでなくても問題ないことを示せばいいので、お気持ちを書きます
p.next[c] == qであるものが集まることでqに属する文字列ができているので、これを集めてp.len + 1以下の長さのものがcloneに属し、p.len + 1よりも大きいものはqに属したままになることがほしい状態です
ここで、qに属するものより短い文字列は別の状態に属していて、それらはp.len + 1よりも小さいので今の所同時に現れているので変更する必要がありません
これで疑問は解決していますが、ほしい状態にcloneとqがなっているかを一応解決しておきます
pからp.linkをたどって得られるsuffixはp.lenよりも短いものだけなのでcloneにはp.len + 1以下でもともとqに属していたものしか属しません
他の遷移はいじっていないのでqには残りのp.len + 1よりも長いものが属したままになっています
よって大丈夫そうであることがわかります
結論
ということでSuffix Automatonの構築でモヤモヤした部分のモヤモヤを少し解消した気持ちになりました
一応これぐらいで最低限は十分かという気持ちに少しなっています
実際にどう使うか知りたいですね、僕はまだわかりません(？)
Suffix ArrayのO(N)構築に比べ実装が圧倒的に軽いのでそこは強そうだけど、使うときに頭が必要そうで怖い
Suffix Arrayは適当にLCPとかこねてればある程度は大丈夫なイメージがあるので...
