Detect Repeated Patterns in Logs

HardPython

Problem

Trend Micro Vision One can inspect network log strings for recurring signatures. Given a log string, detect every distinct pattern of a specified length that appears at least twice within one contiguous sliding window.

Return patterns in the order they are first confirmed as repeated. A pattern should appear only once in the result, even if it repeats in multiple windows. Occurrences may overlap.

Formal Specification

Implement detect_repeated_patterns(logs, pattern_length, window_length).

logs is a string of lowercase English letters representing a normalized log stream.
pattern_length is the length of each pattern to inspect.
window_length is the length of each sliding window.
Return a list of distinct strings, each of length pattern_length.

Two occurrences qualify if both complete substrings fit inside some window of length window_length. Equivalently, their starting indices differ by at most window_length - pattern_length.

Constraints

1 <= len(logs) <= 10^5
1 <= pattern_length <= window_length <= len(logs)
logs contains only lowercase English letters
Overlapping occurrences are valid

Function Signature

def detect_repeated_patterns(logs, pattern_length, window_length):

Return patterns in the order they are first confirmed as repeated. A pattern should appear only once in the result, even if it repeats in multiple windows. Occurrences may overlap.

Formal Specification

Implement detect_repeated_patterns(logs, pattern_length, window_length).

logs is a string of lowercase English letters representing a normalized log stream.
pattern_length is the length of each pattern to inspect.
window_length is the length of each sliding window.
Return a list of distinct strings, each of length pattern_length.

Two occurrences qualify if both complete substrings fit inside some window of length window_length. Equivalently, their starting indices differ by at most window_length - pattern_length.