Cut and Paste - #607 div2 c - tac

#文字列

解法

例
s = 231

231
23131
23131131131
...
となるが,
まず prefix がどの文字列でも同じことに注目
よって, 付け加えるだけ

また, cut で s の末尾の数が必要だが, せいぜい $10^6$ 以下
x 文字以上を構成する必要はないことを, 以下, editorial の補足で示す

editorialの補足

$S^t = S^{t - 1} + S^{t - 1}_{t + 1 ...} * (S^{t - 1}_t - 1)$
例
$S^{t - 1}$ = 231
mode で, l = 1
cut で, s = 2, $S^{t - 1}_{t + 1 ...}$ = 31
s の末尾( $S^{t - 1}_t$ )の 2 回, paste して, $S^t$ = 23131
言い換えると, $S^{t - 1}$ = 231 に 2 - 1 = 1 回, 31をつける

長さでいうと,
$| S^t | = | S^{t - 1} | + | S^{t - 1}_{t + 1 ...} | * (S^{t - 1}_t - 1)$
$| S^t | = | S^{t - 1} | + ( | S^{t - 1} | - t) * (S^{t - 1}_t - 1)$ $\ \ \ \ (1)$

t - 1 番目の文字列の長さ | $S^{t - 1}$ | から t 番目の文字列の長さ | $S^t$ | を求める
(1) より, t 番目の文字列を求める必要はないことがわかる
$S^{t - 1}$ を s, c に cut したとき, | $S^{t - 1}$ | と | s | から | c | がわかる

ポイント

時間計算量がO(N^2)にならないこと
ある長さの文字列をsに付け加えていく
その付け加える文字列の取得, それを何回か s に付け加えるのは並列である
取得や貼り付けの長さは合計 $10^6$ 以下
よって O(N)

コード

https://codeforces.com/contest/1281/submission/67629619

editorial

https://codeforces.com/blog/entry/72212