**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" .

**Edit: (Answer)**

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 .

###### Asked By : URL87

#### Answered By : Yuval Filmus

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

###### Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/14234

**3200 people like this**

## 0 comments:

## Post a Comment

Let us know your responses and feedback