SamCoding Round 10 (Div. 4) D - Bead Necklace
- サイト
- SamCoding
- コンテスト
- SamCoding Round 10 (Div. 4)
- 問題
- D - Bead Necklace(常設版)
英小文字からなる文字列 が与えられます。 が ( を何度も繰り返した文字列)の先頭部分になるような、最も短い文字列 を求める問題です()。
とします。長さ の は の先頭 文字に決まり、条件は「すべての で 」、つまり の 文字目以降(0 始まり)が の先頭部分になっていることです。
これは Z algorithm で調べられます。Z algorithm は、各 について と の 文字目以降の最長共通接頭辞の長さ を で求めます。条件は と同じなので、これを満たす最小の を探し、先頭 文字を出力します。そのような がなければ、 全体が答えです。
計算量は です。
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 は上の を求める関数です。
使用ライブラリ:cpp_include@cb82602