World's most popular travel blog for travel bloggers.

# Pattern bonding problem

, ,
Problem Detail:

Let $\Sigma = {1,2,3,4}$ . We say that symbol $\sigma$ bonds with symbol $\tau$ if $\sigma = \tau$ of $\sigma = \tau +1$ for even $\sigma$ and $\sigma = \tau -1$ for odd $\sigma$ . In other words , 1 and 2 bond , and 3 and 4 bond (in addition to every number bonding with itself ) .

The Pattern bonding problem is defined as follows:

INPUT : Text $T = t_{1} , ..., t_{n}$ and pattern $P = p_{1} , ..., p_{m}$ over alphabet $\Sigma$ .

OUTPUT : All locations $i$ in the text that bond with the pattern , i.e , where $t_{i+j-1}$ bonds with $p_{j}$ $j=1,...,m$ .

Can someone supply an algorithm for the pattern bonding problem (the faster the better complexity can) ? , I thought about "Less then matching" .

Map $(1,2) \rightarrow \alpha , (3,4)\rightarrow \beta$ then the text and the pattern is on $\Sigma = {\alpha , \beta}$ and then we know to solve it in $O(n)$ using witness or KMP .

#### Answered By : Yuval Filmus

Hint: map $1,2$ to $a$ and $3,4$ to $b$.