Suffix Automaton

概要

文字列 $S$ のSuffix Automatonとは、ざっくりいうととても性質のいいDFA(決定性オートマトン)である。一番代表的な性質は次のとおりである。

$S$ の部分文字列全て、またそれらのみを受理する。
頂点数，辺数が $O(|S|)$、より正確には $|V| \leq (2|S| - 1), |E| \leq (3|S| - 4)$
$O(|S|)$ 時間で構築可能

このようなオートマトンが存在するということがまず非自明なのだが、これらに加えて、更に様々な良い性質がある。

構築

構成

最初に、どのようなオートマトンを作るのか(および、存在性の証明)を示す。結論から言うと、Suffix Automatonは$\mathrm{rev}(S)$のCompressed Suffix Treeから機械的に作ることが出来る。

例えば、$S = "babcc"$、つまり $\mathrm{rev}(S) = "ccbab"$ の場合、Suffix Treeは次のようになる。黒色のノードは、そのノードを終端とする Suffix が存在することを表す。

f:id:yosupo:20210131160146j:plain

「次数 $1$ かつ白色のノード」を子のノードとマージしたものがCompressed Suffix Treeである。これと、$S$ の Suffix Automaton が次のようになる。

f:id:yosupo:20210131160121j:plain

ここで、左右のノードは一対一対応している。実際に、ノード7について、受理する文字列の集合が(revすると)全く同一である。他のノードに対しても同じ性質が成り立つ。

このようなAutomatonが必ず存在することが、次の定理によりわかる。証明は容易なので略する。

Compressed Suffix Treeの(根以外の)任意のノードについて、受理する文字列たちから最初の文字を削除した集合は、いくつかのノードの受理する文字列たちの直和で表せる。

実際に、Compressed Suffix Treeの各ノードについて、上記の直和のノードたちから最初の文字で遷移を貼るだけでSuffix Automatonが構築できる。

頂点数 / 辺数

頂点数は明らかに線形である(一般に、$n$ 個の文字列からパトリシアを作ると頂点数は$O(n)$になる)。

辺数はまずSuffix Automatonから(有向)全域木を取る。当然これの辺数はノード数 - 1である。全域木に含まれない辺それぞれについて、(全域木のパス + 含まれない辺)から生成される文字列たちを考える。すると

全て $S$ の部分文字列
文字列の間に、「片方が片方のprefix」という関係はない

が成立するので、文字列の個数 = 全域木に含まれない辺数は高々 $|S|$

アルゴリズム

Compressed Suffix Tree / Suffix Automaton を対応を意識しながら並列で構築する。KMPアルゴリズムのように、$S$ の後ろ($\mathrm{rev}(S)$の先頭)に一文字ずつ文字を追加していく。これは Compressed Suffix Treeでは、(新しい)文字列全体をSuffix Treeに追加することに対応する。

Compressed Suffix Tree / Suffix Automatonの情報として、次の情報を持つ。

$\text{next}(\text{node}, \text{char})$ : Suffix Automatonの辺
$\mathrm{link}(\mathrm{node})$ : Compressed Suffix Treeでの親ノード
$\mathrm{len}(\mathrm{code})$ : nodeが受理する最長の文字列の長さ(=Suffix Treeでの一番下のノードの深さ)
$\mathrm{last}$ : $S$ 全体を入れた時に受理するノード

lenだけ不自然に感じるが、構築で必要になる。

構築においての本質は、Suffix Automatonの次の性質である。

(非空の文字列) $S$ の最後の文字を削除した文字列を $S'$ とする。Compressed Suffix Treeでの $S'$ / $S$ のパス上のノードを $n'1, n'2, \cdots, n'l$ / $n_1, n_2, \cdots, n_m$ とする($n'1 = n_1 = \mathrm{根}$)。このとき、$\mathrm{根}, \mathrm{next}(n'1, x), \mathrm{next}(n'2, x), \cdots, \mathrm{next}(n'_l, x)$ をランレングス圧縮したものが、$n_1, n_2, \cdots, n_m$ となる。

構築では、新しい文字を後ろに追加した後この性質を満たすように様々な値をいじればよい。

実際には新しいノードを作り、 $\mathrm{last}$ からlinkをたどっていく。そして

$\mathrm{next}(n, x)$ が存在しない間 $\to$ 新しく作ったノードに$\mathrm{next}(n, x)$を張っていく
$\mathrm{next}(n, x)$ が存在する場合。ノード $m = \mathrm{next}(n, x)$を分割(Clone)しないといけない場合がある。この判定に $\mathrm{len}$ を使う。$\mathrm{len}(n) + 1 = \mathrm{len}(m)$ ならば Cloneする必要がない。
- 分割するためには、新規ノードを追加する。これはSuffix Treeで根から近い側に対応する。更に$m = \mathrm{next}(n, x)$ の間linkを辿り、nextを新規ノードに張り替える必要があることに注意。

構築の計算量について考える。頂点数、辺数が線形であるので大部分は大丈夫だが、唯一怪しいのは「ノードをCloneした後にnextを張り替える」部分である。実際には、「Compress Suffix Treeでの $\mathrm{last}$ ノードの高さ」をポテンシャルとすることで抑えることが出来る。

性質

その他の性質を列挙する

Suffix Automatonは「Sの部分列、またそれのみを受理する」DFAの中で頂点数が最小(らしい)
$S$ のSuffixと、cloneされてないノードたちは1対1対応する。

拡張

Compressed Suffix Treeが自然に複数の文字列に対応できるように、Suffix Automatonも対応できる。

lastを初期化して文字列追加、を同じ Suffix Automaton に繰り返せば良い。ここで、新しいノードが生まれない場合もあることに注意。

問題例

$S$ の部分文字列の種類数

DAGのパスの総数となるので、DP出来る
各頂点 $n$ について$\mathrm{len}(n) - \mathrm{len}(\mathrm{link}(n))$ を足すだけでもよい(これはCompressed Suffix Treeでのパスの長さ=受理する文字列数に対応する)。

$S, T$の共通部分列の種類数

$S$, $T$, $S$ + "$" + $T$ の部分列の個数から計算できる。
${ S, T }$ から Suffix Automaton を作ることで直接計算できる。$S$ のSuffix, $T$ のSuffixのどちらからも到達可能なノードのみについて$\mathrm{len}(n) - \mathrm{len}(\mathrm{link}(n))$を足せば良い

参考

使用例

AC code of Number of Substrings

struct SuffixAutomaton {
    struct Node {
        unordered_map<char, int> next;
        int link, len;
    };
    vector<Node> nodes;
    int last;

    SuffixAutomaton() {
        nodes.push_back({{}, -1, 0});
        last = 0;
    }

    void push(char c) {
        int new_node = int(nodes.size());
        nodes.push_back({{}, -1, nodes[last].len + 1});
        int p = last;
        while (p != -1 && nodes[p].next.find(c) == nodes[p].next.end()) {
            nodes[p].next[c] = new_node;
            p = nodes[p].link;
        }
        int q = (p == -1 ? 0 : nodes[p].next[c]);
        if (p == -1 || nodes[p].len + 1 == nodes[q].len) {
            nodes[new_node].link = q;
        } else {
            // clone node (q -> new_q)
            int new_q = int(nodes.size());
            nodes.push_back({nodes[q].next, nodes[q].link, nodes[p].len + 1});
            nodes[q].link = new_q;
            nodes[new_node].link = new_q;

            while (p != -1 && nodes[p].next[c] == q) {
                nodes[p].next[c] = new_q;
                p = nodes[p].link;
            }
        }
        last = new_node;
    }
};

int main() {
    string s;
    cin >> s;

    SuffixAutomaton sa;
    for (char c : s) {
        sa.push(c);
    }

    int m = int(sa.nodes.size());
    ll ans = 0;
    for (int i = 1; i < m; i++) {
        ans += sa.nodes[i].len - sa.nodes[sa.nodes[i].link].len;
    }

    cout << ans << endl;
    return 0;
}

2020-08-08

AGC 046 E Permutation Cover

解けずに解説読んだ

本質

答えが-1かどうか <=> (max < 2*min)に気づくかどうか
[1, 1, ..., 1, 2, 2, ..., 2]のパーツができる <=> ↑の条件は全部できる

思考反省

方向性を間違えた

出来た: 辞書順最小なので判定条件出来たが使わなかった: パーツごとに独立間違えた方針: 先頭のごちゃごちゃとかがあるから判定条件を書き下すのは無理だろう　考えたくねえ -> きっとなんらかの貪欲が最適なことが証明可能で、これを実装すればいいんだろう正しい方針: とりあえず先頭にごちゃごちゃがない場合の判定条件を考える。

2020-07-30

競プロ実装テクニック

これはなに

実装力で戦える！～競プロにおける実装テクニック14選～ - Qiita に触発された

競技プログラミングでコーディングの際気を付けていること - うさぎ小屋を強く参考にしている

効果が高い or 一般性がありそう　なことから書いたつもり

重要なこと

「競プロのきれいなコードと業務のきれいなコードは違う」と定期的に唱える。未来の自分 or 他の人が読む必要がないことを仮定できるため、様々なバッドノウハウ(業務)が正当化される。(あえて過激なことを書くと、)「using namespace stdを使わない」などは逆にバッドノウハウ(競プロ)だと思っている。

-fsanitize=undefined,address / -D_GLIBCXX_DEBUG

#include <iostream>

using namespace std;

int main() {
    int a[10];
    cout << a[100] << endl; 
    return 0;
}

このコードは当然未定義動作だが、これを g++ main.cpp -g -fsanitize=undefined,address とコンパイルして実行すると

A.cpp:7:13: runtime error: index 100 out of bounds for type 'int [10]'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior A.cpp:7:13 in

などと出てくる。他にも様々な未定義動作をキャッチできる。速度に影響があるが、手元で使わない理由はないと思う。他にも-D_GLIBCXX_DEBUGをコンパイルオプションに入れると色々検知するようになるが、macで使えない…

当然ながら g++ main.cpp -g -fsanitize=undefined,address などといちいち打つのは時間の無駄なので、aliasなどの機能を適時使うと良い。

コーディングスタイル

コーディングスタイル(インデント, space/tab, ...)は揃ってないより揃ってたほうがいい。有名規約で言うと Google C++ Style Guide に従っている人が身近では多い気がする。

インデントを手で整えるのは時間の無駄なので、エディタの自動整形に任せるべき。自分は以下の.clang-formatでvscodeに全部任せている。

BasedOnStyle: 'Chromium'
IndentWidth: 4
AccessModifierOffset: -2

# for competitive programing
AllowShortFunctionsOnASingleLine: All
AllowShortIfStatementsOnASingleLine: true
AllowShortLoopsOnASingleLine: true
AlwaysBreakTemplateDeclarations: false

いわゆる「きれいな」コーディングスタイルが(競プロで)常に正しいかというと怪しい。例えば1 * 2 + 3 * 4と1*2 + 3*4なら後者のほうが読みやすいと思う(自分はもう手癖で入れてしまうが…)。

using namespace std

575とも呼ばれる。std::があらゆるところから消せるのでコードがスッキリする。名前空間が汚染されるというデメリットがあるが、引っかかるのは無視できるぐらいの確率なので圧倒的にメリットのほうが大きいと思う。

マクロ / スニペット

マクロは俗に言う

#define rep(i, n) for (int i = 0; i < n; i++)
#define all(v) v.begin(), v.end()

みたいなやつ。僕はマクロは使っていないがfori / all でこれらが出てくるスニペットを登録している。マクロを使っても競プロなら何のデメリットもない。

とりあえず手でいちいちfor (int i = 0; i < n; i++)を書いているならば見直したほうがいい。

printfデバッグ /デバッガ

個人的には多くの場合でデバッガよりprintfデバッグのほうが速いと考えているが、デバッガのほうが強いときもある。assertで落ちたときにスタックトレースを確認するなど。僕は雑にlldbを使うが、これは改善の余地がある気がする。

printfデバッグするにしろ、printfをいちいちつけたり消したりするのは時間の無駄、僕は以下のようなマクロ(を強化したもの)を使っている。

また、vector / mapなども簡単に出力できるようにするといい。operator<<をオーバーロードするなど

#ifdef LOCAL
#define dbg(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl
#else
#define dbg(x) true
#endif

goto

競プロでもgotoを使ってメリットが有るタイミングは少ないと思うが例外もある、有名な例は多重ループの大域脱出がある。

bool ok = false;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        if (solve(i, j)) {
            ok = true;
            break;
        }
    }
    if (ok) break;
}

が

bool ok = false;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        if (solve(i, j)) {
            ok = true;
            goto loop_out;
        }
    }
}
loop_out:

のように書けるというやつ。2重だとありがたみが薄いが、競プロでは平然ともっと多重のループが出てくるので、そういう時に強い。

bool ok = [&]() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (solve(i, j)) return true;
        }
    }
    return false;
}();

このようにも書け、自分はこちらをよく使う。

再帰ラムダ

普通にdfsを書こうとすると

vector<vector<int>> g;

void dfs(int v, int parent) {  
    for (int u: g[v]) {
        if (u == parent) continue;
        dfs(u, v);
    }
}

int main() {
    dfs(0, -1);
}

となるが、これを

int main() {
    vector<vector<int>> g;

    auto dfs = [&](auto self, int v, int parent) -> void {
        for (int u: g[v]) {
            if (u == parent) continue;
            self(self, u, parent);
        }
    };
    dfs(dfs, 0, -1);
}

と書ける。独特な記法を覚える必要があるが、処理を上から下へと書けるのは大きい。なお、ラムダ式は覚えると便利な事が多いので慣れると吉。

vector<vector<>>を短く書けるようにする

個人的おすすめ。V<int> / VV<int>でそれぞれvector<int> / vector<vector<int>>になるようにしている。便利。

2020-03-03

WTF C2 Triangular Lamps Hard 別解法

今回は、Nimberを使ってWTF C Triangular Lamps Easy / Hardを解いていこうと思います。

C1

このような問題では、操作で変わらない不変量を考えたくなります

具体的には $(x, y)$ に $\binom{x + y}{x} \pmod 2$ を書き込めば、 $(x \geq 0, y \geq 0)$ では不変量です。なのでこれを適切にシフトしたものを考えて、うまくやるとOKです

C2

先述の不変量は一般の場合ではあまり役に立ちません。なぜならば、1の数が少なすぎるからです。つまり不変量を求めたところで元の点に関して得られる情報量が少なすぎます。

じゃあどうするかというと、元々の想定解法では先述の不変量を同時に大量にばら撒きます。もちろん適切に計算できるようなばらまきかたをしないといけなくて、そういうことを考えると自然と $\bmod 3$ が出てきます。

今回はもっと情報量の多い不変量を考えることにします。

実際に、ある $a$ について、 $(x, y)$ に $a^ x (a+1)^ y$ を書き込むと、これは不変量になっています。ただし、要素は全て $\mathbb{F}_ {2^N}$ とします。 $\bmod 2$ でダメなら $\mathbb{F}_{2^N}$ というのは自然ですね。

この不変量により、 $a$ を原子根にすると、 $(a + 1) = a^s$ として、 $x + sy$ が求まります。もう一つ、他のaについても調べると、ある $t$ について $x + ty$ が求まります。

結果として、 $x, y$ が求まりました。

実装としては、 $F_{2^N}$ で離散対数を求める必要があります。ところで、最近Nimberで離散対数を求める問題が出ました: Problem - F - Codeforces　ちょうどいいですね。

実装例: Submission #10507304 - World Tour Finals 2019 Open Contest

2020-01-02

Library Checkerを支える技術

あけましておめでとうございます。これは Competitive Programming (2) Advent Calendar 2019 - Adventar の 14日目の記事です。あけましておめでとうございます。

この記事では、Library Checker の宣伝をします

Library Checkerって？

競プロのライブラリを整備するために爆誕したサイトです。特徴としては、問題が全部ライブラリを整備する目的に特化していること、ケースジェネレーター、チェッカーなどが全て公開されていることが大きな特徴です

中身を全て公開することにより

誰でも問題の追加が出来る
誰でもケースの修正などが出来る
CIに組み込める*1

などの、様々な利点を得ることが出来ます。理論上はO(使用人数)でケースが強くなっていくので、最強のテストケースが出来ると言う目論見です。

概要

こんな感じです

f:id:yosupo:20200101233401p:plain — こういう図をブログに貼りたかった

見ての通り、GCP(Google Compute Platform)で動いています。

一つ一つ紹介していきます

Problems

library-checker-problems で問題の情報を管理しています。

ジェネレーターとかは全部C++で、それをpythonから叩く仕組みになっています。目的上どの環境でも同じテストケースを吐き出すようにしないといけないので、とても苦労しています。(uniform_int_distributionは環境依存なんですよ、知っていましたか？)

Cloudbuild

図にやたら出てくるやつです。yamlファイルにコマンドを書き並べるだけで、githubにpushするたびに実行とかをやってくれるので乱用しています。今5種類ぐらい使っています。

ジャッジサーバー

dockerなどの既存のコンテナは時間計測 / メモリ計測がむずかったので、いっそのことと思い、unshare / cgroups / overlayfs などの(dockerの中で使われてる技術たち)を直接叩き、コンテナを作っています

unshare: プロセスからネットワークのアクセスを禁止したり、mountを分離したりしてくれるすごいやつ
cgroups: これがないと何も出来ない。プロセスのCPU、メモリ消費量とか諸々を制限してくれるすごいやつ
overlayfs: プロセスから/tmpとか変な場所にファイルを書き込んでも、パッとやるとそれらを一瞬でなかったことにしてくれるすごいやつ

ずっとサーバー借りてると高いので、preemptible(AWSのスポットインスタンスみたいなもの)を借り続けるという雑なことをしています。24時間(or もっと短い)で勝手に停止してしまうので、停止を検出したらCloud Functions(≒ AWS Lambda)で自動再起動、うまくいくのかと思いましたが、今のところうまくいっています。

SQL

Cloud SQLと言うフルマネージドのサービスでPostgre SQLを立てています。バックアップなども取ってくれているようなので慢心しています。

このサービスのコアで、全てが入っています。問題のテストケースもbytea型でそのまま入っています　ええんかこれ？

APIサーバー

(最近正式サービスとなった)Cloud Runで動いています。理由はApp engineだとgRPCが動かなかったからです。 apiv1.yosupo.jp:443 で動いていて、API一覧は library-checker-judge/library_checker.proto at master · yosupo06/library-checker-judge · GitHub です。(RESTではないので、GitHub - ktr0731/evans: Evans: more expressive universal gRPC client のようなgRPCクライアントを使わないと何も見れないです)