# Non-Overlapping Pattern Matching in Event Stream
## Problem Statement
You are given an event stream as a string $S$, consisting of uppercase English letters. Each letter represents a distinct type of telemetry event (e.g., 'A' for harsh acceleration, 'B' for harsh braking, etc.).
You are also provided with a list of $k$ pattern strings, $P = \{P_1, P_2, \dots, P_k\}$, where each $P_i$ is a sequence of events to be detected.
Your task is to find the total number of non-overlapping occurrences of *any* of the patterns from the list $P$ within the event stream $S$.
The matching process follows these rules:
1. Start searching for a match from the current position in $S$. Initially, this is the beginning of $S$ (index $0$).
2. If multiple patterns from $P$ match a substring of $S$ starting at the current position, you must always choose the match corresponding to the *longest possible pattern*.
3. Once a pattern $P_i$ of length $|P_i|$ is matched at the current position, it counts as one occurrence. The search then continues from the position immediately following this matched pattern. That is, if a match of length $L$ is found at index $j$, the next search begins at index $j+L$.
4. If no pattern matches at the current position, the search advances by one character (i.e., from index $j$ to $j+1$).
5. The process continues until the end of the string $S$ is reached.
## Input Format
The input consists of multiple lines:
- The first line contains the event stream string $S$.
- The second line contains a single integer $k$, representing the number of patterns in the list $P$.
- The next $k$ lines each contain a pattern string $P_i$.
## Output Format
Output a single integer representing the total number of non-overlapping pattern occurrences found in $S$, following the longest-match priority rule.
## Sample Test Cases
### Sample Input 1
```
ABCABCDAB
3
AB
CD
ABC
```
### Sample Output 1
```
3
```
## Constraints
- The length of the event stream string $S$ is between $1$ and $10^5$ characters, i.e., $1 \le |S| \le 10^5$.
- The number of patterns $k$ is between $1$ and $100$, i.e., $1 \le k \le 100$.
- The length of each pattern string $P_i$ is between $1$ and $1000$ characters, i.e., $1 \le |P_i| \le 1000$ for all $1 \le i \le k$.
- All characters in $S$ and $P_i$ are uppercase English letters ('A' through 'Z').
- Time limit: 1 second
- Memory limit: 256 MB
## Explanation
Let's trace the matching process for Sample Input 1:
$S = \text{"ABCABCDAB"}$
$P = \{\text{"AB"}, \text{"CD"}, \text{"ABC"}\}$
1. **Current position: index $0$** (character 'A')
* Substring $S[0 \dots]$: "ABCABCDAB"
* Patterns matching from index $0$:
* "AB" matches $S[0 \dots 1]$
* "ABC" matches $S[0 \dots 2]$
* Prioritizing the longest match, we choose "ABC" (length $3$).
* Count = $1$.
* Next search starts at index $0 + 3 = 3$.
2. **Current position: index $3$** (character 'A')
* Substring $S[3 \dots]$: "ABCDAB"
* Patterns matching from index $3$:
* "AB" matches $S[3 \dots 4]$
* "ABC" matches $S[3 \dots 5]$
* Prioritizing the longest match, we choose "ABC" (length $3$).
* Count = $2$.
* Next search starts at index $3 + 3 = 6$.
3. **Current position: index $6$** (character 'D')
* Substring $S[6 \dots]$: "DAB"
* Patterns matching from index $6$:
* "CD" does not match.
* "AB", "ABC" do not match.
* No pattern matches.
* Next search starts at index $6 + 1 = 7$.
4. **Current position: index $7$** (character 'A')
* Substring $S[7 \dots]$: "AB"
* Patterns matching from index $7$:
* "AB" matches $S[7 \dots 8]$
* Prioritizing the longest match, we choose "AB" (length $2$).
* Count = $3$.
* Next search starts at index $7 + 2 = 9$.
5. **Current position: index $9$**
* End of string $S$ is reached. The search terminates.
The total number of non-overlapping occurrences is $3$.
Loading problem statement...