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 .
