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

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.

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

• 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. Commented Feb 9, 2022 at 17:16
• 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. Commented Feb 11, 2022 at 1:04
• @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. Commented Mar 5, 2022 at 21:54
• 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. Commented Mar 5, 2022 at 22:52