1803. The Most Copies You Can Cut Out
Given a text t and a pattern p, print the largest number of occurrences of p
inside t that can be chosen so that no two of them share a character.
Occurrences may NOT overlap here, and a COUNT is wanted rather than positions. That single restriction is the whole difference from problem 1802.
aaaa, aa -> 2 three occurrences exist, only two fit apart
aabaabaab, aabaab -> 1 the two occurrences overlap, so one must go
abcabc, abc -> 2 these touch without overlapping, which is allowed
ababab, ab -> 3
Touching is allowed: an occurrence ending at position 2 and another starting at position 3 share nothing.
## What most people try first
Counting every occurrence, as problem 1802 does, and reporting that. On aaaa
with aa it answers 3 where the answer is 2, and on aabaabaab with aabaab
it answers 2 where the answer is 1. Both were confirmed by running it.
The other instinct is to search for the best SUBSET of occurrences, which is a
selection problem over up to n items.
## Take every match the moment it completes
Scan left to right with the prefix-function automaton. Whenever a full match completes, count it and reset the automaton state to 0, which forbids any later match from reusing those characters.
pi = prefix function of p
j = 0
for each character c of t:
while j > 0 and c != p[j]: j = pi[j-1]
if c == p[j]: j = j + 1
if j == m: count = count + 1; j = 0
The reset to 0, rather than to pi[m-1], is the entire change from an
overlapping count.
## Why greedy is optimal here
Take any best selection. Its first chosen occurrence starts no earlier than the first occurrence in the text. Replacing it with that earliest occurrence keeps the selection legal, because the replacement ends no later, so it cannot collide with anything later in the selection. Repeating the argument left to right turns any best selection into the greedy one without ever losing a copy. So greedy achieves the maximum.
## Cost
O(n + m). The naive alternative, testing the pattern at every position, is
(n - m + 1) * m: about 2 * 10^8 comparisons at n = 200000 and
m = 1000, against about 4 * 10^5 here.
Constraints - `1 ≤ length of t ≤ 200000` - `1 ≤ length of p ≤ 200000` - both strings contain only lowercase English letters - `p` may be longer than `t`, in which case the answer is 0
Input
The first line contains the text t.
The second line contains the pattern p. Both are lowercase English letters.
Output
Print one integer on its own line: the largest number of occurrences of the pattern that can be chosen with no two of them sharing a character.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.