Find motif in packed signal
Your task
A capture card stores a long signal packed as runs to save space. run_chars[i] holds the character of run i and run_lengths[i] holds how many times it repeats, so the signal is every run written out in order. Neighbouring runs never carry the same character, every run length is at least 1, and a single run can be a billion characters long, so writing the signal out in full is not an option. Given the packed runs and a short motif, return how many times motif occurs in the signal. Occurrences may overlap, so aa occurs 4 times inside a run of 5 a characters. Return 0 when motif is empty, when there are no runs, or when motif is too long to fit.
Examples
packed_run_hit_count(run_chars: list[str], run_lengths: list[int], motif: str) -> intExample 1
Input
packed_run_hit_count(["a", "b", "a"], [5, 1, 2], "aa")Output
5Example 2
Input
packed_run_hit_count(["a", "b"], [3, 4], "aab")Output
1Example 3
Input
packed_run_hit_count(["x"], [1000000000], "xx")Output
999999999