A sensor writes its tape in squeezed form: each letter is followed by a count, so "a3b2"
stands for "aaabb". Write count_on_tape(tape, phrase) that returns how many times the
expanded phrase occurs in the expanded tape. Occurrences may overlap, and every starting
position counts once.
Both strings use the same format:
- a lowercase letter followed by a positive decimal count with no leading zeros;
- the same letter may appear in two neighbouring runs (
"a2a3"means"aaaaa").
tape may be empty (the empty text); phrase is never empty.
Examples
Input: tape = "a3b2a4b2c1", phrase = "a2b2"
Output: 2
Explanation: the tape is aaabbaaaabbc and "aabb" starts at positions 1 and 7.
Input: tape = "x2x3y1", phrase = "x4"
Output: 2
Explanation: the tape is xxxxxy; "xxxx" starts at positions 0 and 1.
Input: tape = "a5b1a5b1a5b1a5", phrase = "b1a5b1"
Output: 2
Constraints
0 <= len(tape) <= 10**6,1 <= len(phrase) <= 1000- every count is between
1and10**9, so the expanded texts can be enormous - the answer fits easily in a Python integer
Goals
- Parse letter-and-count runs and merge runs that repeat a letter
- Match a pattern run by run without expanding either text
- Treat the first and last pattern runs differently from the inner runs