CF 102697085 - Pattern Two

The task asks us to decide whether a string contains a repeated substring that appears exactly the requested number of times consecutively. Unlike the previous pattern problem, the repeated section is allowed to begin at any position in the input string.

codeforcescompetitive-programming

CF 102697085 - Pattern Two

Rating: -
Tags: -
Solve time: 1m 25s
Verified: yes

Solution

Problem Understanding

The task asks us to decide whether a string contains a repeated substring that appears exactly the requested number of times consecutively. Unlike the previous pattern problem, the repeated section is allowed to begin at any position in the input string. Characters before the repetition and after the repetition do not matter. The repeated block itself must contain at least two characters, following the rule established by the preceding problem in the contest. The official statement gives a string on the first input line and the required repetition count on the second line, and the answer is True or False.

For example, with abcXYZXYZXYZdef and a requested count of 3, the substring XYZ is repeated three times, so the answer is True. With abcXYXYdef and a requested count of 3, only two copies of XY occur, so that particular pattern does not satisfy the request.

The statement does not provide an explicit maximum length for the input string. That changes how we should reason about complexity. A direct cubic search can become expensive surprisingly quickly, while an O(n²) solution gives a much safer bound for a one-second limit. Since there is no published numeric bound for n, we should avoid relying on a tiny fixed string length even though this is an introductory contest problem. The official limits are one second and 256 MB.

There are several edge cases that a naive implementation can mishandle. First, the repeated block must have at least two characters. For input

aaaaa
2

the correct output is True, because aa occurs twice consecutively. A careless solution that only searches for a repeated character could accept the input for the wrong reason, while a solution that accidentally allows a block of length one may report patterns that the preceding problem explicitly forbids.

A second edge case is that the repetition does not have to start at position zero. For input

xxabcabcabczz
3

the correct output is True. A solution inherited directly from the previous problem and only checking prefixes would incorrectly return False, because the useful repetition starts at index 2.

A third edge case is irrelevant text after the repetition. For input

abcabcXYZ
2

the correct output is True. The abcabc section is a valid two-copy repetition and the trailing XYZ is ignored. This is explicitly part of the intended pattern behavior.

Finally, a repetition can have a longer repeated run than the requested count. For input

HELLOHELLOHELLOHELLOHELLO
4

the answer is still True, because four consecutive copies of HELLO form a valid repeated section, with the remaining copy treated as surrounding text. The phrase “precisely matches” refers to the selected repetition section having the requested number of copies, not to requiring the entire maximal run in the input to contain exactly that many copies.

Approaches

The most direct brute-force approach is to try every possible starting position and every possible length of the repeated block. For a start position i and block length L, we construct the candidate block s[i:i+L] and compare the following k - 1 blocks with it. If all of them match, we have found the required pattern.

This approach is correct because every possible repeated section has some starting position and some block length, so enumerating both parameters cannot miss a valid answer. The problem is the amount of repeated work. There can be O(n²) choices of (i, L), and checking one candidate can inspect O(kL) characters. With k treated as part of the input, the worst case is cubic in the string length, and even for a fixed small k the total work remains Θ(n³). A string of length 1000 can already lead to hundreds of millions of character-level comparisons in the worst case.

The useful observation is that, once the starting position and block length are fixed, we do not really need to compare all copies independently. Suppose the candidate starts at i and has length L. The condition that k copies are equal is exactly

S[i : i + (k-1)L] = S[i+L : i+kL].

In other words, the suffix beginning at i must agree with the suffix beginning at i+L for at least (k-1)L characters.

This is exactly the kind of query answered by a Z-function. For a suffix beginning at i, the Z value at offset L tells us the length of the longest common prefix between that suffix and the suffix beginning L characters later. If that value is at least (k-1)L, then the first k blocks of length L are identical.

We compute a Z-array separately for each possible starting position. Computing the Z-array for a suffix of length m costs O(m), and the lengths of all suffixes add up to O(n²). After obtaining the Z-array for one starting position, checking all possible block lengths costs another O(n), giving an overall O(n²) algorithm.

Approach Time Complexity Space Complexity Verdict
Brute Force O(n³) O(n) Too slow in the worst case
Optimal O(n²) O(n) Accepted

Algorithm Walkthrough

  1. Read the string s and the requested repetition count k. If k < 2, return False, because a repetition requires at least two copies of a block.
  2. Let n be the length of the string. A repeated block must contain at least two characters and must fit k times inside the remaining suffix. For a starting position start, the largest possible block length is therefore (n - start) // k.
  3. For each possible start, build the Z-array of the suffix s[start:]. In this Z-array, z[L] is the length of the longest prefix of s[start:] that is also equal to the substring beginning L characters later.
  4. Try every block length L from 2 through (n - start) // k. We need k copies of this block, so the first copy must match the next k - 1 copies for a total of (k - 1) * L characters.
  5. If z[L] >= (k - 1) * L, the substring beginning at start consists of at least k consecutive copies of the same block. Return True immediately.
  6. If every starting position and every possible block length fails, return False.

The key invariant is that for a fixed start, z[L] exactly measures how many characters after the first block continue to agree with the string shifted by L positions. Consequently, z[L] >= (k-1)L is equivalent to equality of all k copies. Since every valid repetition has some start and some block length, the nested search considers every possible answer, and the algorithm can only return True when the required equality actually holds.

Python Solution

import sys
input = sys.stdin.readline

def has_pattern(s: str, k: int) -> bool:
    n = len(s)

    if k < 2:
        return False

    for start in range(n):
        m = n - start

        if m < 2 * k:
            continue

        t = s[start:]
        z = [0] * m

        left = right = 0

        for i in range(1, m):
            if i < right:
                z[i] = min(right - i, z[i - left])

            while i + z[i] < m and t[z[i]] == t[i + z[i]]:
                z[i] += 1

            if i + z[i] > right:
                left = i
                right = i + z[i]

        max_len = m // k

        for length in range(2, max_len + 1):
            if z[length] >= (k - 1) * length:
                return True

    return False

def solve():
    s = input().rstrip("\n")
    k = int(input())
    print("True" if has_pattern(s, k) else "False")

if __name__ == "__main__":
    solve()

The has_pattern function contains the complete algorithm. The early k < 2 check handles an invalid repetition count before any string processing begins.

For every start, t represents the suffix beginning at that position. We build its Z-array using the standard [left, right) matching window. When i lies inside the current window, the value from the corresponding mirrored position can be reused as a lower bound, avoiding unnecessary character comparisons.

The loop over length begins at 2, rather than 1, because the repeated block must have at least two characters. The upper bound is m // k, because a block longer than that cannot fit k times in the suffix.

The condition z[length] >= (k - 1) * length is the central implementation detail. We do not need to construct block * k, and we do not need to compare each copy separately. The Z value already represents the entire comparison between the first copy and everything after it shifted by one block.

There is no integer overflow issue in Python. The largest expression involving the repetition count is (k - 1) * length, which Python handles with arbitrary-precision integers.

The input string is read with rstrip("\n") rather than strip(), because spaces are legitimate characters in the string and must remain part of the input.

Worked Examples

For the first example, the input is the official sample:

uyboubawlefjbasdHELLOHELLOHELLOHELLOsygvfubklkj
4

At the beginning of the string there is no useful repetition. Eventually start reaches the first H of HELLO.

start candidate length required Z value actual Z value result
16 2 6 less than 6 reject
16 3 9 less than 9 reject
16 4 12 less than 12 reject
16 5 15 15 accept

The block length is 5, so (k-1)L = 3 * 5 = 15. The suffix beginning at the first H matches the suffix beginning five characters later for 15 characters, exactly covering the next three copies. The algorithm returns True. This matches the official sample output.

A second example demonstrates why the starting position cannot be assumed to be zero:

xxabcabcabczz
3
start candidate length required Z value actual Z value result
0 2 4 less than 4 reject
1 2 4 less than 4 reject
2 2 4 less than 4 reject
2 3 6 6 accept

At start = 2, the block is abc. Three copies require six matching characters after the first copy, and the Z value at offset 3 is 6. The algorithm accepts the string without requiring the repeated section to begin at the first character.

Complexity Analysis

Measure Complexity Explanation
Time O(n²) A Z-array of every suffix costs O(n²) in total, and the block-length checks also total O(n²)
Space O(n) Only the current suffix and its Z-array are stored

The official time limit is one second and the memory limit is 256 MB. Since the statement does not publish a maximum string length, an O(n²) solution is a safer choice than the cubic brute force. The algorithm also avoids storing an O(n²) table, so its memory usage remains linear.

Test Cases

import sys
import io

def has_pattern(s: str, k: int) -> bool:
    n = len(s)

    if k < 2:
        return False

    for start in range(n):
        m = n - start

        if m < 2 * k:
            continue

        t = s[start:]
        z = [0] * m

        left = right = 0

        for i in range(1, m):
            if i < right:
                z[i] = min(right - i, z[i - left])

            while i + z[i] < m and t[z[i]] == t[i + z[i]]:
                z[i] += 1

            if i + z[i] > right:
                left = i
                right = i + z[i]

        for length in range(2, m // k + 1):
            if z[length] >= (k - 1) * length:
                return True

    return False

def run(inp: str) -> str:
    old_stdin = sys.stdin
    sys.stdin = io.StringIO(inp)

    s = sys.stdin.readline().rstrip("\n")
    k = int(sys.stdin.readline())

    ans = "True" if has_pattern(s, k) else "False"

    sys.stdin = old_stdin
    return ans + "\n"

# Provided sample
assert run(
    "uyboubawlefjbasdHELLOHELLOHELLOHELLOsygvfubklkj\n4\n"
) == "True\n", "sample 1"

# Minimum useful repetition
assert run("abab\n2\n") == "True\n", "minimum repeated block"

# Repetition starts after irrelevant text
assert run("xxabcabcabczz\n3\n") == "True\n", "nonzero starting position"

# Requested number is too large
assert run("abcabc\n3\n") == "False\n", "not enough repetitions"

# A single-character block must not count
assert run("aaaa\n3\n") == "False\n", "block length must be at least two"

# More copies than requested are still enough to select the requested section
assert run("HELLOHELLOHELLOHELLOHELLO\n4\n") == "True\n", "longer run"

# Boundary case where the pattern reaches the end exactly
assert run("zzxyxyxy\n3\n") == "True\n", "pattern reaches string end"

# No repeated section
assert run("abcdefgh\n2\n") == "False\n", "no repetition"
Test input Expected output What it validates
abab, 2 True Smallest valid repeated block
xxabcabcabczz, 3 True Repetition can start away from the beginning
abcabc, 3 False Insufficient number of copies
aaaa, 3 False A one-character block is not a valid pattern
HELLO repeated five times, 4 True Surrounding text can exist beyond the selected repetition
zzxyxyxy, 3 True Repetition ending exactly at the final character
abcdefgh, 2 False Completely non-repeating input

Edge Cases

For the minimum valid block length, consider

abab
2

The algorithm reaches start = 0 and tries length = 2. The suffix is abab, while the suffix shifted by two positions is ab. The Z value at offset 2 is 2, which equals (2-1) * 2. The algorithm returns True. A solution that accidentally starts its length loop at 3 would miss this valid pattern.

For a pattern that does not begin at the first character, consider

xxabcabcabczz
3

The first two positions are rejected because no suitable three-copy pattern begins there. At position 2, the candidate block abc has length 3. The Z value at offset 3 is 6, while the required value is (3-1) * 3 = 6. The algorithm returns True, correctly ignoring the xx prefix and zz suffix.

For an input where there are not enough copies, consider

abcabc
3

The only plausible repeated block has length 2 or 3, but three copies would require at least six characters for a two-character block and nine characters for a three-character block. The only six-character candidate is abcabc, which contains two copies, not three. Every candidate fails the Z threshold, so the answer is False.

For the minimum block-size restriction, consider

aaaa
3

The string contains three copies of a, but the repeated block has length one. Since the pattern inherited from the previous problem requires the repeated string to contain at least two characters, the algorithm never tests length = 1. It returns False.

For extra copies, consider

HELLOHELLOHELLOHELLOHELLO
4

At the first H, length = 5 gives a Z value large enough to cover three subsequent copies. The algorithm accepts immediately. The fifth HELLO does not invalidate the selected four-copy repetition because the problem allows irrelevant text around the repeated section.