I mönstret som matchar med d jokertecken problem får man en text T av längd n och ett mönster P av längd m som innehåller d jokertecken tecken, var och en betecknar med en speciell symbol '?'. En jokertecken tecken matchar alla andra tecken. Målet är att för varje m-längds delsträng av T fastställa om den matchar P. I den strömmande modellen varianten av mönstret som matchar med d jokertecken problem texten T anländer ett tecken i taget och målet är att rapportera, innan nästa tecken anländer, om de sista m tecken matchar P medan endast o(m) ord i rymden. I detta papper introducerar vi två nya algoritmer för d wildcard mönster matchande problem i streaming modellen. Den första är en randomiserad Monte Carlo-algoritm som parameteriseras av en konstant 0 ≤ δ ≤ 1. Denna algoritm använder Õ(d 1−δ ) avkortad tid per tecken och O(d 1+δ ) ord i rymden. Den andra algoritmen, som används som en svart låda i den första algoritmen, är en randomiserad Monte Carlo algoritm som använder O(d + log m) värsta fall tid per karaktär och O(d log m) ord av utrymme.
Golan m.fl. REF studerar mönster matchande problem med ett litet antal jokertecken i den strömmande modellen.
Streaming Pattern Matching with d Wildcards
{'venue': 'Algorithmica', 'journal': 'Algorithmica', 'mag_field_of_study': ['Computer Science', 'Mathematics']}