How to match a string with any linear transformation of the pattern?

Question

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.

Answer 1

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()