Blocks Hidden in a Tape

Hard

The string text is printed text_times times in a row to make one long tape. The string pattern written pattern_times times in a row is called a block. You may strike out any characters of the tape, keeping the rest in their original order. Find the largest integer m such that striking out characters can leave the block repeated m times in a row. If not even one block can be formed, return 0. For example, with text = "ab" and text_times = 2 the tape is "abab", and with pattern = "b" and pattern_times = 2 the block is "bb"; the tape yields exactly one such block.

Example 1

text="xyz", text_times=3, pattern="xz", pattern_times=1 → 3

The tape is "xyzxyzxyz". Striking out every y leaves "xzxzxz", three copies of the block "xz".

Example 2

text="ab", text_times=5, pattern="ba", pattern_times=2 → 2

The tape is "ababababab", which can be cut down to "babababa": 4 repeats of "ba", so 2 blocks "baba".

Example 3

text="abc", text_times=4, pattern="d", pattern_times=1 → 0

The letter d never appears on the tape, so not even one block can be formed.

Constraints

1 ≤ len(text) ≤ 1000
1 ≤ len(pattern) ≤ 100
1 ≤ text_times, pattern_times ≤ 10⁶
text and pattern consist of lowercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

String Dynamic Programming

Similar problems

Pattern With Dot and Star Hard Longest Balanced Bracket Stretch Hard Does the Text Fit the Pattern Hard Shuffle by Cutting and Swapping Hard Ways to Cross Out Hard

Input

text="xyz", text_times=3, pattern="xz", pattern_times=1

Expected

Run checks the first 3 tests in your browser. Submit checks all 111 tests on the server, hidden ones included.