String Matching with Wildcards in the Massively Parallel Computation Model
MohammadTaghi Hajiaghayi, Hamed Saleh, Saeed Seddighin, Xiaorui Sun · 2021
We study distributed algorithms for string matching problem in presence of wildcard characters. Given a string T (a text), we look for all occurrences of another string P (a pattern) as a substring of string T. Each wildcard character in the pattern matches a specific class of strings based on its type. String matching is one of the most fundamental problems in computer science, especially in the fields of bioinformatics and machine learning. Persistent effort has led to a variety of algorithms for the problem since 1960s.