1
$\begingroup$

The following exercise in my homework is about string matching using the $KMP$ algorithm with a pattern that can be modified by a linear transformation.

Question: We're given a text $T \in \mathbb{N}^*$ where $|T|=n$ and a pattern $P \in \mathbb{N}^*$ where $|P|=m$, in other words $T$ and $P$ are consisted of natural numbers (an example appears below). We're required to describe a linear algorithm that finds all the matches in $T$ with the pattern $P'$ such that: $$P'=cP+k$$ for every $c\in \mathbb{R} \neq 0$ and $k\in \mathbb{R}$. Note that $c$ and $k$ aren't given and we have to find them.

For example: let $T=(3,7,9,5,0,0,3)$, $P=(1,3,4)$. In this situation we have a matching in the first 3 numbers if we let $c=2$ and $k=1$.

I have a solution for this question but it has a problem with it so if anyone could help. Here is my algorithm:

  1. Create $P'$ such that $P'[i]=P[i]-P[i+1]$ for every $1\leq i\leq n-1$.
  2. Create $P''$ such that $P''[i]=\frac {P'[i]} {P'[i+1]}$ for every $1\leq i\leq n-2$.
  3. Do same things that We've done with $P$ for $T$ and get $T''$.
  4. Run $KMP$ with text $T''$ and pattern $P''$.

My algorithm works until there are $0$'s in $P'$ or $T'$. The example above will divide by 0 to get $P''[4]$. I tried to let $\frac x 0 = 0$ for every $x\in \mathbb{R}$ but it won't work if we take for example $T=4221$ and $P=3221$. I had an idea to skip the 0's if there is while making $P''$ and $T''$ but I don't know really how to describe this. I know it should work but it is hard to describe.

$\endgroup$

1 Answer 1

2
$\begingroup$

Your idea of extracting the ratios of successive differences between the adjacent numbers is brilliant.

Let $P''$ retain all needed information

The $0$'s in $P'$ or $T'$ pose some difficulty in producing the ratios. Your idea of "skipping the $0$'s" is the right approach. In order to make your idea working, we should also track how many $0$s are skipped.

At step 2, instead of dividing by $P'[i+1]$, divide $P'[i]$ by the nonzero number in $P'$ at the smallest index $j\lt i$. We have to keep track of the difference between $j$ and $i$ as well.

Since $c\neq 0$, if $P'[i]$ matches $T'[j]$, then both of them are zeros or none of them is $0$, i.e., it cannot happen that exactly one of them is $0$. So The information whether a number in $P'$ or $T'$ is $0$ or not is critical. If it is $0$, then whether the number before it is $0$ or not can be helpful information as well.

Following the ideas above, here is one way to create $P''$.

  • if $P'[i]==0$,
    • if $i== 1 $ or $P'[i-1]==0$, let $P''[i] = (555555, -1)$
    • otherwise, let $P''[i] = (55555, -2)$
  • Otherwise,
    • if there is no nonzero element before index $i$ in $P'$, let $P''[i] = (55555, -3)$.
    • else, suppose $j$ is the index of last such element. Let $P''[i] = (P'[i]/P'[j], i-j)$

When $P''[i]$ is one of $(55555,-1)$, $(55555,-2)$ and $(55555, -3)$, the second parts, $-1, -2, -3$ carries all the information in $P''[i]$. The first parts, $55555$, are padded so that $P''[i]$ is always a pair of numbers for all $i$.

Create $T''$ from $T'$ in the same way.

What does "match" mean?

How can we apply/tweak KMP algorithm to process $P''$ and $T''$ so that we will find all affine transformation of $T'$ in $P'$? The key point is to customize the meaning of "$P''[i]$ matches $T''[j]$" to suit our purpose.

They match if

  • either they are the same,
  • or the second part of $T''[[j]$ is $-3$ -- which means all elements before index $j$ in $T'$ are $0$s and the second part of $P''[i]$ is greater than $j+1$ -- which means all $j$ elements before index $i$ in $P'$ are $0$s).

An implementation in Python

The arrays/lists in the explanation above start at index 1. Of course, when it comes to Python, all lists start at index 0.

def get_ratios(numbers):
    """Return the enriched ratio of ratios of successive differences between
     the adjacent numbers. 55555 is used only for padding."""
    n = len(numbers)
    diffs = [numbers[i + 1] - numbers[i] for i in range(n - 1)]

    to_previous_index = [-1] * n  # of nonzero element in diffs
    index_of_previous_nonzero = -1
    for i in range(n - 1):
        to_previous_index[i] = index_of_previous_nonzero
        if diffs[i]:
            index_of_previous_nonzero = i

    def compute_enriched_ratio(index):
        if diffs[index] == 0:
            return (55555, -1) if index == 0 or diffs[index - 1] == 0 \
                    else (55555, -2)
        else:
            if to_previous_index[index] == -1:
                ratio = (55555, -3)
            else:
                ratio = (
                    diffs[index] / diffs[to_previous_index[index]],
                    index - to_previous_index[index])
            return ratio

    ratios = [compute_enriched_ratio(i) for i in range(1, n - 1)]
    return ratios


def is_matched(pattern, j, nums, i):
    """return whether pattern[j] matches nums[i]"""
    return pattern[j] == nums[i] or (pattern[j][1] == -3 and nums[i][1] > j + 1)


def compute_partial_match_table(pattern):
    """ return an array the element of which at index i is the length of
    the longest suffix of pattern[0:i] that matches a prefix of the pattern"""
    m = len(pattern)

    pmt = [0] * m
    pmt[0] = 0
    longest = 0  # length of the previous longest prefix suffix
    i = 1
    while i < m:
        if is_matched(pattern, longest, pattern, i):
            longest += 1
            pmt[i] = longest
            i += 1
        else:
            if longest:
                longest = pmt[longest - 1]  # i is not increased
            else:
                pmt[i] = 0
                i += 1

    return pmt


def find_all_matches_with_affine_transformation(pattern, nums):
    """return all indices such that for each index j, there exists an affine
    transformation of `pattern` that is a prefix of `nums[j:]`"""
    m, n = len(pattern), len(nums)
    if m > n:
        return []
    if m == 1:
        return list(range(n))
    if m == 2:
        if pattern[0] == pattern[1]:
            return [i for i in range(n - 1) if nums[i] == nums[i + 1]]
        else:
            return [i for i in range(n - 1) if nums[i] != nums[i + 1]]

    ratios_pattern = get_ratios(pattern)
    ratios_nums = get_ratios(nums)

    # KMP algorithm
    pmt = compute_partial_match_table(ratios_pattern)

    m -= 2
    n -= 2
    j = 0  # index of current number in pattern
    i = 0  # index of current number in nums
    matches = []
    while i < n:
        if is_matched(ratios_pattern, j, ratios_nums, i):
            i += 1
            j += 1

        if j == m:
            matches.append(i - j)
            j = pmt[j - 1]

        elif i < n:  # mismatch after j matches
            if j != 0:  # since pattern[0..lps[j-1]] matches
                j = pmt[j - 1]
            else:
                i += 1
    return matches


def demo():
    pattern = [1, 3, 4]
    nums = [3, 7, 9, 5, 0, 0, 3]
    indices = find_all_matches_with_affine_transformation(pattern, nums)
    for i in indices:
        print("starting at index", i, nums[i: i + len(pattern)])
    # starting at index 0 [3, 7, 9]


demo()
$\endgroup$
4
  • $\begingroup$ First of all thanks for the answer. Also since you already answered and if you can complete the solution and give an answer for the case where all after $P'[i]$ is zeros. Also what you do think we should do if for example $P=(0,0,0)$ and $T=(9,8,7,6,0,0,0,0,0)$, here we have 3 appearances of $P$ in $T$ where $c\in \mathbb{R}$ and $k=0$. I hope you can answer both of my questions. $\endgroup$
    – Mohamad S.
    Feb 9, 2022 at 17:16
  • $\begingroup$ I wrote several examples on a paper and as you said the algorithm is really tricky, I found 3 different cases where the algorithm completely fails to handle it, I will write it all tommorow along with a solution the I thought of. $\endgroup$
    – Mohamad S.
    Feb 11, 2022 at 1:04
  • $\begingroup$ @CSStudent What is the language of your choice? I can write a program in it, so that you can run it to your satisfaction to verify my algorithm is correct. It is easy to prove mathematically with some labor as well; however, it can hardly be more enlightening than the description of the algorithm in the answer. $\endgroup$
    – John L.
    Mar 5, 2022 at 21:54
  • 1
    $\begingroup$ Actually, I was just searching for a description for an algorithm, not a program that implements it, the course is theoretically, not implementation, your answer of description was more than enough for me but I really forgot to reply to it and verify it. It's now verified and also thank you very much for your hard work. $\endgroup$
    – Mohamad S.
    Mar 5, 2022 at 22:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.