コンテンツにスキップ

Z algorithm

タグ「Z algorithm」の記事 1 件

SamCoding Round 10 (Div. 4) D - Bead Necklace

英小文字からなる文字列 ss が与えられます。ss が ppp…pppp\ldots p(pp を何度も繰り返した文字列)の先頭部分になるような、最も短い文字列 pp を求める問題です(∣s∣≤106|s| \le 10^6)。

∣s∣=n|s| = n とします。長さ ii の pp は ss の先頭 ii 文字に決まり、条件は「すべての j≥ij \ge i で sj=sj−is_j = s_{j-i}」、つまり ss の ii 文字目以降(0 始まり)が ss の先頭部分になっていることです。

これは Z algorithm で調べられます。Z algorithm は、各 ii について ss と ss の ii 文字目以降の最長共通接頭辞の長さ ziz_i を O(n)O(n) で求めます。条件は zi=n−iz_i = n - i と同じなので、これを満たす最小の i≥1i \ge 1 を探し、先頭 ii 文字を出力します。そのような ii がなければ、ss 全体が答えです。

計算量は O(n)O(n) です。

C++
#include "shogo-library/base/all"
#include "shogo-library/string/string.hpp"
void solve() {
STR(S);
auto z = z_algorithm(S);
rep(i, 1, len(S)) {
if (z[i] == len(S) - i) {
print(S.substr(0, i));
return;
}
}
print(S);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

z_algorithm は上の ziz_i を求める関数です。

使用ライブラリ:cpp_include@cb82602