CF 314B - Sereja and Periods

Rating: 2000
Tags: binary search, dfs and similar, strings
Solve time: 1m 5s
Verified: yes

Solution

Problem Understanding

We are given two strings, a and c, and two integers, b and d. The string a is repeated b times to form a long string w, and the string c is repeated p times to form another string q. The task is to find the largest integer p such that q can be obtained from w by deleting some characters without rearranging the remaining ones. In other words, q must be a subsequence of w. The output is this maximum p, or 0 if no positive integer works.

The bounds b and d go up to $10^7$, while the strings themselves are at most length 100. This indicates that we cannot explicitly construct the full strings w and q, because their lengths could reach $10^9$. Instead, any solution must work with the base strings and their repetition counts efficiently. A naive solution that repeatedly builds the repeated strings will exceed memory limits and runtime constraints.

Non-obvious edge cases include when c contains letters not present in a, or when c is longer than a and b is small. For example, if a = "abc", b = 2, c = "abcd", d = 1, there is no way to form c even once from a repeated twice, so the output should be 0. A careless solution that ignores character frequency mismatches or that attempts a greedy approach without proper accounting can produce incorrect answers.

Approaches

The brute-force approach would be to try constructing w explicitly by repeating a b times, and then attempt to form q by matching c repeatedly. Each attempt would iterate through w to count how many times c fits as a subsequence. This works in principle, but the worst-case complexity is $O(b \cdot |a| \cdot p \cdot |c|)$, which can reach $10^{16}$ operations - clearly impractical.

The key insight is that we do not need the entire string. The problem reduces to counting how many times we can find c as a subsequence within the repeated pattern of a. By focusing on indices and transitions within a, we can simulate how c progresses through multiple repetitions of a efficiently. We precompute, for each starting position in a and for each character in c, where the next matching character occurs. This allows us to "jump" through a without iterating character by character, giving a linear-time solution in terms of |a| * |c|.

With this approach, we repeatedly apply this precomputed subsequence matching until we exhaust b repetitions of a. The result is the maximum number of times c fits (p), divided by d since q is c repeated d times.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(b *	a	* p *
Optimal	O(	a	*

Algorithm Walkthrough

Compute the length of a (la) and c (lc). Initialize a pointer pos in a to zero. This pointer will simulate traversing the repeated a string without actually constructing it.
Initialize a counter count_c to zero. This will track how many times we successfully match c as a subsequence in the repeated a.
Iterate while the total traversed a repetitions are less than b. For each character in c, find the next occurrence of that character in a starting from pos. If we reach the end of a, increment a repetition counter and reset pos to zero. This simulates moving to the next copy of a.
Each time we complete matching c once, increment count_c. Continue until we cannot match c anymore because we have used all b repetitions of a.
Finally, divide count_c by d (integer division) to get the maximum p, since q consists of c repeated d times.

Why it works: The algorithm maintains the invariant that pos represents the current position in the repeated a where the next character match should start. By jumping to the next occurrence of the needed character and counting repetitions of a, we accurately simulate subsequence matching without building the full strings. This guarantees that count_c represents the exact number of c sequences obtainable from w, and integer division by d produces the correct maximum p.

Python Solution

import sys
input = sys.stdin.readline

b, d = map(int, input().split())
a = input().strip()
c = input().strip()

la, lc = len(a), len(c)

# Precompute next occurrence positions in `a` for each character
next_pos = [{} for _ in range(la)]
last_seen = {}
for i in reversed(range(la)):
    last_seen[a[i]] = i
    next_pos[i] = last_seen.copy()

# Helper to find next position of char `ch` from index `i` in `a`
def find_next(i, ch):
    if ch in next_pos[i]:
        return next_pos[i][ch]
    return None

pos = 0
rep_count = 0
count_c = 0

while rep_count < b:
    for ch in c:
        next_i = find_next(pos, ch)
        if next_i is None:
            rep_count += 1
            if rep_count >= b:
                print(count_c // d)
                sys.exit()
            pos = 0
            next_i = find_next(pos, ch)
            if next_i is None:
                print(count_c // d)
                sys.exit()
        pos = next_i + 1
        if pos == la:
            pos = 0
            rep_count += 1
            if rep_count > b:
                print(count_c // d)
                sys.exit()
    count_c += 1

print(count_c // d)

This solution carefully simulates matching c as a subsequence through repeated a. It precomputes the next occurrence of each character to avoid iterating linearly over a each time, handles boundary transitions between repetitions, and correctly tracks the count of c sequences.

Worked Examples

Sample 1

Input:

10 3
abab
bab

Step	pos	rep_count	count_c	Matching character
Start	0	0	0	b
Match b	1	0	0	a
Match a	2	0	0	b
Match b	3	0	0	End of c
Complete c	3	0	1	-
Repeat until rep_count=10	...	10	9	-

count_c = 9, divide by d = 3 → p = 3.

This trace shows that c can be matched 9 times in 10 repetitions of a, giving 3 full sequences of q.

Custom Input

3 2
abc
ac

Step	pos	rep_count	count_c	Matching character
Start	0	0	0	a
Match a	0	0	0	c
Match c	2	0	0	End of c
Complete c	3	1	1	-
Repeat	...	3	3	-

count_c = 3, divide by d = 2 → p = 1.

This shows that partial matching of c across a repetitions is handled correctly.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(	a
Space	O(	a

Given the constraints |a| ≤ 100, |c| ≤ 100, b ≤ 10^7, the algorithm easily runs in under 1 second and stays within 256 MB memory.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    b, d = map(int, input().split())
    a = input().strip()
    c = input().strip()

    la, lc = len(a), len(c)
    next_pos =