定期宣伝

弊社はエンジニアを熱烈募集しています. 以下から気軽にカジュアル面談申し込んでください. 就職・転職を考えている知人にも積極的に宣伝してください.

Spir | Smart scheduling calendar

この勉強会の宣伝もお願いします. 参加者が増えるほど質や頻度が上がると思います. #Acompany競プロ勉強会 で実況や感想,質問を呟くなども.

不定期宣伝

Acompanyからの暗号文 #2

暗号文を作りました。 12月までに解くと抽選で5名にAcompanyのTシャツが当たります。

第一回も抽選期間は終わりましたが問題自体はとても面白いです:Acompanyからの暗号文 #1

記号

文字列 $S$ に対して 0-indexed で添え字を振り、 $S[i]$ で $i$ 文字目を表す。 例えば $S=\mathrm{mississippi}$ の場合 $S[0]= \mathrm{m}, S[1] = \mathrm{i}, S[8] = \mathrm{p}$ となる。

また、 $S$ の部分文字列 $S[l] S[l+1] \cdots S[r-1]$ を $S[l,r)$ で表すことにする。 例えば $S=\mathrm{mississippi}$ の場合 $S[2,6) = \mathrm{ssis}$ となる。

Z algorithm

長さ $n$ の文字列 $S$ に対して、以下を満たす長さ $n$ の数列 $z$ を $\Theta(n)$ 時間で求めるアルゴリズム。

$$ z_i = \max\{k\mid S[i,i+k)= S[0,k)\} $$

つまり、各 $i\in[0,n)$ について $z_i$ は $S$ と $S[i,n)$ の最長共通接頭辞の長さ。

普通に計算しようとすると $\Theta(n^2)$ 時間かかる

def z_algorithm(s: str) -> list[int]:
    n = len(s)
    z = []
    for i in range(0, n):
        k = 0
        while i + k < n and s[i + k] == s[k]:
            k += 1
        z.append(k)
    return z

したがって $\Theta(n)$ 時間で解くためには何かしらの高速化が必要。

ac-library に入っているくらいには汎用的なアルゴリズム。