A function to return 1 if and only if two strings match in a certain number of characters

29 Views Asked by At

I want to formulate equation for comparing two strings $A$, and $B$ each of length $x$. The function should be $1$ if they are matching in at least $x-l$ characters. Otherwise the function should be $0$.

$$ \text{match}(A,B,x,l) = \begin{cases} 1, & \text{????} \\ 0, & \text{else} \end{cases} $$

I want to figure out the condition as shown in the formula above.

1

There are 1 best solutions below

0
On

You could try some recursive definition:

\begin{align} \text{cmatch}(\epsilon, \epsilon, 0, l) &= 0 \\ \text{cmatch}(u, v, x, l) &= 0 \quad (l < 0) \\ \text{cmatch}(u, v, x, l) &= 0 \quad (l \ge x ) \\ \text{cmatch}(au, av, x, l) &= 1 + \text{cmatch}(u, v, x - 1, l - 1) \\ \text{cmatch}(au, cv, x, l) &= 0 + \text{cmatch}(u, v, x - 1, l) \\ \text{cmatch}(au, gv, x, l) &= 0 + \text{cmatch}(u, v, x - 1, l) \\ \text{cmatch}(au, tv, x, l) &= 0 + \text{cmatch}(u, v, x - 1, l) \\ \text{cmatch}(cu, av, x, l) &= 0 + \text{cmatch}(u, v, x - 1, l) \\ & \vdots \\ \text{cmatch}(tu, tv, x, l) &= 1 + \text{cmatch}(u, v, x - 1, l - 1) \\ \text{match}(u, v, x, l) &= \begin{cases} 1, & \text{cmatch}(u, v, x, l) \ge x - l \\ 0, & \text{else} \end{cases} \end{align}