String Pattern Matching Algorithms

An $\mathbf{\text{alphabet }}$$\mathrm{\Sigma }$ is a finite set. A $\mathbf{\text{symbol}}$ is an element $s\in \mathrm{\Sigma }$. A $\mathbf{\text{string}}$ is a finite sequence of symbols, i.e, elements of an alphabet. The set of all strings over $\mathrm{\Sigma }$ is denoted by ${\mathrm{\Sigma }}^{\ast }$. We say a string $p\in {\mathrm{\Sigma }}^{\ast }$ is a $\mathbf{\text{pattern}}$ over a fixed alphabet $\mathrm{\Sigma }$ if $p$ consists of symbols from $\mathrm{\Sigma }$ Let $s$ be a string and denote $s:=s_1\cdots s_n$. We say that a subsequence $s_i\cdots s_j$ of $s$ is a $\mathbf{\text{substring}}$ of $s$. A $\mathbf{\text{ocurrence}}$ of $u$ in $s$ is a pair $(i,j)$ such that $u:=s_i\cdots s_j$ is a substring of $s$.

Let $P$ be a set of patterns over a fixed alphabet $\mathrm{\Sigma }$ and let $T$ be a fixed string. The Multiple Pattern String Matching (MPSM) is the problem of finding all occurrences of all patterns of $P$ in $T$. The Single Pattern String Matching (SPSM) is a special case of (MPSM) by adding the constraint $|P|=1$.

The Multiple Pattern String Matching is one of the basic string algorithms problems and several algorithms have been proposed to solve it. There are practical solutions to real-world problems that can be developed using these algorithms, including, but not limited to, intrusion detection systems, evolutionary biology, computational linguistics, and data retrieval.

---

Proposal

Poster

Monography

Implementations