import std; void main () { string S = readln.chomp; const int N = S.length.to!int; string y = "yukicoder"; const int M = y.length.to!int; bool f (int x) { string pat = replicate(y, x); string X = pat ~ S; auto z = zAlgorithm(X); foreach (i; pat.length .. z.length) { if (pat.length <= z[i]) { return true; } } return false; } auto ret = bsearch!(f)(0, (N + M - 1) / M); writeln(ret.value); } void read (T...) (string S, ref T args) { import std.conv : to; import std.array : split; auto buf = S.split; foreach (i, ref arg; args) { arg = buf[i].to!(typeof(arg)); } } int[] zAlgorithm (T) (const T[] S) { const int N = cast(int) S.length; auto ret = new int[](N); if (N == 0) { return ret; } ret[0] = N; int i = 1, j = 1; // S[0 .. j - i) = S[i .. j)を保つ。 while (i < N) { if (j < i) { j = i; } // LCPを広げる。 while (j < N) { if (S[j - i] != S[j]) { break; } j++; } ret[i] = j - i; // 計算を再利用する。 int k = 1; while (k <= i && i + k < j && i + k + ret[k] < j) { ret[i + k] = ret[k]; k++; } i += k; } return ret; } unittest { import std.algorithm: equal; assert(equal(zAlgorithm("abcbcba"), [7, 0, 0, 0, 0, 0, 1]), "test1"); assert(equal(zAlgorithm("mississippi"), [11, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]), "test2"); assert(equal(zAlgorithm("ababacaca"), [9, 0, 3, 0, 1, 0, 1, 0, 1]), "test3"); assert(equal(zAlgorithm("aaaaa"), [5, 4, 3, 2, 1]), "test4"); assert(equal(zAlgorithm(""), new int[](0)), "test5"); } import std.traits : isIntegral; import std.int128 : Int128; class NoTrueRangeException: Exception { import std.exception: basicExceptionCtors; mixin basicExceptionCtors; } class BsearchException: Exception { import std.exception: basicExceptionCtors; mixin basicExceptionCtors; } struct BsearchResult (T) { import std.format: format; private bool has_value = true; private T l, r; private T _value; this (T _l, T _r) { this.l = _l; this.r = _r; this.has_value = false; } this (T _l, T _r, T _value) { this.l = _l; this.r = _r; this._value = _value; } bool empty () { return !this.has_value; } T value () { if (this.empty()) { throw new NoTrueRangeException( format("No true condition found in the range [%s, %s].", l, r)); } return _value; }; } BsearchResult!T bsearch (alias func, T) (T l, T r) if ((isIntegral!(T) || is(T == Int128)) && !is(T == byte) && !is(T == ubyte) && !is(T == short) && !is(T == ushort)) { import std.traits : isCallable, ReturnType, Parameters; import std.meta : AliasSeq; static assert(isCallable!(func)); static assert(is(ReturnType!(func) == bool)); static assert(is(Parameters!(func) == AliasSeq!(T))); import std.algorithm.comparison : min, max; T L = l, R = r; if (l == r) { if (func(l)) return BsearchResult!(T)(L, R, l); return BsearchResult!(T)(L, R); } while (min(l, r) + 1 < max(l, r)) { T m = midpoint(l, r); if (func(m)) { l = m; } else { r = m; } } bool lb = func(l); if (!lb) return BsearchResult!(T)(L, R); bool rb = func(r); if (rb) return BsearchResult!(T)(L, R, r); if (!rb) return BsearchResult!(T)(L, R, l); throw new BsearchException(format("This code path should never be reached. l: %s, r: %s.", L, R)); } T midpoint (T) (T a, T b) if (isIntegral!(T) || is(T == Int128)) { static if (is(T == short) || is(T == ushort) || is(T == byte) || is(T == ubyte)) { import std.conv : to; int x = a, y = b; return midpoint(x, y).to!(T); } else { import std.math.algebraic : abs; import std.algorithm.comparison : min, max; int as = (0 <= a) ? 1 : -1, bs = (0 <= b) ? 1 : -1; if (as == bs) { if (as == 1) { return min(a, b) + (max(a, b) - min(a, b)) / 2; } return max(a, b) + (min(a, b) - max(a, b)) / 2; } return (a + b) / 2; } }