Week of Code 27: How Many Substrings?

(追記2018年12月26日)読めるように書いてない文章なので、読まなくてもよいです。suffix automaton について知りたいなら、解説記事もちらほらみかけますが、すなおに論文を読むのがはやいです。link cut tree はあまりいい記事や論文はなくて、でもいわれているほど難しい概念でもないので、iwi さんのスライドを読むのがいいのではないでしょうか。

(追記 2017/9/13)ポテンシャル云々言ってますが、よく考えるとスプレー木のポテンシャルは気にしなくていいです。そこまで立ち入って解析しても計算量が落ちるわけではないため、HL分解の解析のみを意識してください。そこまで需要のある記事ではないと思うので、本文をわざわざ書き換えたりはしませんが、その点よろしくお願いします。

どうせ平方分割だろうと思って editorial を覗いてみたら、想像以上に解法が面白かった。editorial を読んでもよく分からなかったので、簡単に解法に至る流れを書き留めておく。

間違ったこと書いていたらごめんなさい。

https://www.hackerrank.com/contests/w27/challenges/how-many-substrings


editorial では suffix tree で説明されているが、自分が知っている ukkonen's algorithm と editorial の説明が上手くマッチしない。なぜか、uwicoder に書かれている suffix automaton に置き換えて読むとマッチする。そのため、以後 suffix tree ではなく suffix automaton について書くことにする。まあ確かに suffix tree なんだけども。

suffix automaton とは

Suffix Automatonの作り方と使い方 - uwicoder - アットウィキ

文字列 S の suffix automaton というのは、文字列 S の全部分文字列を受理するオートマトンのことである。たとえば abaab の suffix automaton は ε, a, aa, ab, aab, abaab などを受理し、bb, abab, aaa などは受理しない。

このようなオートマトンを頂点数、辺数 O(|S|) でオンラインに構築できる、というのが驚くべき事実である。

原理自体は KMP や palindromic tree 等を知っていれば、よくある感じだ。詳細はここには書かない。

uwicoder にも書かれているとおり、suffix automaton を用いることにより「Tに含まれる相異なるsubstringの個数を求める」ことができる。uwicoder で紹介されているのはDPによる方法だが、今回はそれは使わない。

性質の項目に書かれている、以下の 4 項目を用いる。

  • ノードxは複数のsubstringに対応するが、それは下のように最短のものがベースとなり、そこの頭に1文字ずつ追加してできる感じの文字列の集合になっている。
  • これらの最長の長さはlen. t0からxへnextを通って行く最長経路長。
  • これらの最短の長さはlink.len+1. t0からxへnextを通って行く最短経路長。
  • これらのsubstringの出現箇所の末尾位置はすべて一致する。

上の 4 つの事実を踏まえれば、部分文字列の総数は

$$ \sum_{x} (x.len-x.link.len) $$

で計算できることが分かる。(最長経路が len になるのは当然で、最短経路が link.len になるのは、linkを辿ったときにすべて suffix が現れることを考えれば当然である。他の性質もよく考えれば成り立つことが分かるだろう。)

このことを踏まえて今回の問題の解くことにする。

D-query

D-query という問題の解法を知っているだろうか。

http://www.spoj.com/problems/DQUERY/

ある区間に含まれる値の種類数を求める問題である。この問題は以下のコメントのように解くことができる。

http://codeforces.com/blog/entry/8962?#comment-146571

重複を除去するためになるべく右側に置いておく、という考え方がこの問題でも使えるので抑えておきたい。とはいっても、知らなくてもさほどの問題はないだろう。

解法

まずクエリ全体を右端をキーにしてソートする。文字列を 1 文字ずつ末尾に追加していき、クエリの右端と一致したタイミングで計算を行う。

suffix automaton の各ノードには「出現する右端の位置」というパラメータを持たせておく。これを rightEnd と呼ぶことにする。

BIT[i]には位置iを左端とする文字列の個数が格納する。すべてのノードxに対して$[x.rightEnd-x.len,x.rightEnd-x.link.len)$に 1 を加算しておけば、$BIT.sum[L,R]$で部分文字列の総数を求めることができる。

suffix automaton に文字を追加したときに、いかにしてこのBITを正しく維持するのかが問題となる。実は link-cut tree を使うとうまくいく。

link-cut tree

link-cut treeに関しては以下に書かれている。

lctree は使う人で用語がぶれやすい気がするので、先に用語だけ定義しておく。

  • splay(x): ノード x を根に持っていく。
  • expose(x): 根とノード x をパスで繋ぐ。別の見方をすると、ノード x を lctree 全体の根に持っていく。

今回はすこし変わった使い方をするので上の 2 つだけ理解していれば問題ない。今回は遅延評価を用いてパス上の rihgtEnd を v に書き換える操作を実装する。ただし、以下の invariant を維持するように lctree を設計する。以降 invariant といったら、この invariant のことを指すことにする。

  • 同一パスに含まれるノードは rightEnd が等しい

expose をやみくもにすると rightEnd の値がバラバラになってしまうため、link/cut 操作はややアドホックな方法を取る。

link

つなぐだけ。当然ではあるが、link(x,y)を呼び出す前に x->p は null を指していなければならない。y の位置次第ではポテンシャルが激増してしまうが、今回はポテンシャルが激増するような使われ方はしないので問題ない。

// parent(x) = y
void link(node *x, node *y) {
    x->link = y;
    x->p = y;
}

cut

xと実際の木における xの親とを切り離す。splay木における split 操作で実現できる。通常の方法ではまず expose(x) をするのだが、invariant を破壊してしまうため splay のみにとどめておく。結果として繋ぎ方の場合分けが増える。

親が同一パスに含まれていた場合は split でうまくいく。ただし expose はしていないので、x の上にスプレー木がある可能性がある。そのため、切ったときに親ポインタの張替えが必要なことに注意。

親が同一パスにない場合は、親は lightEdge で結ばれているはずなので親ポインタを null にするだけでよい。

計算量は、splay操作がアクセス補題により $O(\log n)$ で、ポインタの張替えはポテンシャルが下がるだけなので $O(1)$ である。ゆえに全体で $O(\log n)$ である。

void cut(node *x) {
    splay(x);
    if (x->p != x->link) {
        x->l->p = x->p;
        x->l = nullptr;
    }
    x->p = nullptr;
}

expose

これは普通の lctree と大差ない。invariant があるので、このパス上のノードに対応する文字列の右端はすべて等しい。このパスに対応する文字列は、最小の長さがこのスプレー木の最左ノード の link.len+1 で、最長の長さが根の len であるような連続した部分文字列である。そのため、rightEnd を一気に pos に置き換えられる。

HL分解の解析により、for ループは全体で $O(n \log n)$ しか回らない。そのため BIT の操作が呼び出される回数は $O(n \log n)$ 回である。

内部でスプレー木の最小ノードを求めているが、アクセス補題により $O(\log n)$ で行える。こちらもHL分解の解析により $O(n \log n)$ 回しか呼び出されない。

ゆえに amortized $O(\log ^2 n)$ で行える。

void expose(node *x, int pos) {
    bool fst = true;
    for (node *r = nullptr, *y = x; y != nullptr; r = y, y = y->p) {
        splay(y);

        node *mn = y;
        while (mn->l) mn = mn->l;
        int beg = mn->link == nullptr ? 0 : mn->link->len;
        int end = y->len;
        splay(mn);
        splay(y);

        if (!fst) {
            bit.add(y->rightEnd - end, y->rightEnd - beg, -1);
        }
        bit.add(pos - end, pos - beg, 1);
        y->r = r;
        fst = false;
    }
    splay(x);
    setLazy(x, pos);
}

append

大分見た目が変わっているが以下のコードを機械的に書き換えたに過ぎない。

http://e-maxx.ru/algo/suffix_automata

link のタイミングがアレで、ポテンシャルが激増するように見えなくもないが、直後に expose(cur) を呼び出しているので、すぐにポテンシャルは下がる。ゆえに問題ない。

void append(char c) {
    node *cur = create();
    cur->len = last->len + 1;
    node *p;
    for (p = last; p != nullptr && !p->next.count(c); p = p->link) {
        p->next[c] = cur;
    }
    if (p == nullptr) {
        link(cur, root);
    } else {
        node *q = p->next[c];
        if (p->len + 1 == q->len) {
            cur->link = q;
            cur->p = q;
        } else {
            node *clone = create();
            clone->len = p->len + 1;
            clone->next = q->next;
            cut(q);
            clone->rightEnd = q->rightEnd;
            for (; p != nullptr && p->next[c] == q; p = p->link) {
                p->next[c] = clone;
            }
            link(clone, q->link);
            link(q, clone);
            link(cur, clone);
        }
    }

    cur->rightEnd = cur->len;

    expose(cur, cur->len);
        
    last = cur;
}

全体のコード。

compressed suffix tree はひたすら使いにくい印象があったので、suffix automaton という概念を知ることができたのは嬉しい。かなり難しいけど、かなり知見がある問題だと思う。