弊社はエンジニアを熱烈募集しています. 以下から気軽にカジュアル面談申し込んでください. 就職・転職を考えている知人にも積極的に宣伝してください.
Spir | Smart scheduling calendar
この勉強会の宣伝もお願いします. 参加者が増えるほど質や頻度が上がると思います. #Acompany競プロ勉強会 で実況や感想,質問を呟くなども.
暗号文を作りました。 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}$ となる。
長さ $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 に入っているくらいには汎用的なアルゴリズム。