Automaton Pattern Hits Problem

Automaton Pattern Hits Problem — ExecCode Hard DSA Practice

Solve the Automaton Pattern Hits problem on ExecCode. Free online hard DSA practice in String. Write and run code in Java, C++, Python — no signup required to run.

Problem description

Count every occurrence of every pattern as a contiguous substring of text, including overlapping hits. Aho-Corasick is the linear multi-pattern automaton. A suffix automaton / suffix array with LCP answers 'does this string appear' and distinct-substring queries. A palindromic tree would be used if the patterns were palindromes. A linear XOR basis is the algebraic analogue when the 'patterns' are bitmasks instead of strings. Return the total number of matches. Overlapping occurrences count separately. Empty patterns contribute 0. You are given: text — haystack string patterns — list of needles Return total occurrence count. A pattern equal to the whole text counts 1. Two identical patterns each add their own hits.

Examples

Input {'text': 'aaa', 'patterns': ['aa', 'a']}; Output 5. Input {'text': 'ababa', 'patterns': ['aba']}; Output 2. Input {'text': 'xyz', 'patterns': ['q', '']}; Output 0

Constraints

Patterns may repeat Matching is case-sensitive Overlaps count

Practice Automaton Pattern Hits free on ExecCode. Browse DSA problems, topic map, and placement guides.