# Longest prefix of string S that is also a sub-prefix of S in linear time

As the question suggest. I want an algorithm that runs in linear time which finds the longest prefix of a substring that is a sub-prefix of the same string.

Formally:

Given a string $$S$$ of length $$n$$, we define a function $$\delta_{S}:$$ $$[n]\rightarrow[n]$$ as follows. For each integer $$w$$, $$1\le w\le n$$, $$\delta$$ is defined:

$$\delta_{S}[w] = \max\{i\colon S[1...i] = S[w...w+i-1]\}$$.

The algorithm should find $$\delta_{S}[w]$$ for each $$1\le w \le n$$.

Question should be solved using the $$\pi$$ function of KMP's preprocessing.

The question can be easily solved in $$O(n^2)$$. The $$O(n^2)$$ solution is simple and straightforward. For each $$w$$, manually find the longest prefix. Each iteration could take $$O(n)$$ time, thus for all $$1 \le w \le n$$ it would take $$O(n^2)$$. However, the question should be solved in a linear time. This question falls down under string matching, in particular, KMP. I know the question should be solved using the function $$\pi$$ from KMP's pre-processing. However, I can't solve the question.

What I tried:

Assume in this answer that all arrays starts from index 1 and ends at index n. Not from 0 until n-1.

Create a new array $$\delta$$. Initialize $$\delta[1]$$ = n, since this is always true, and initialize the rest of the array to be 0.

Create an array $$\pi$$ and compute $$\pi(w)$$ for $$1\le w \le n$$, and then for each index, subtract the index of the cell of the array from the content of the array. For instance, $$i-\pi(i)$$ and then check if this value is greater from $$\delta[i]$$. However, I seem to get stuck and can't solve the problem. I've tried to solve the problem for a couple of days before posting here, I can't seem to really fully understand the question and how to approach it.

• If you construct a suffix tree/suffix array, does this become easy to solve?
– D.W.
Feb 7, 2023 at 1:27
• Actually yes, it makes easier to solve and I haven't noticed that it becomes much easier to solve it by a suffix tree. However, I'm required to solve this question using the pi function from KMP preprocessing. Additionally, I'd really like to understand how can I really solve it using KMP's preprocessing function. Feb 7, 2023 at 1:32
• You were asked to compute something called the z-function (cp-algorithms.com/string/z-function.html). Feb 7, 2023 at 20:21
• Isn't this the function computed by KMP itself? can you explain how this is different? Feb 21, 2023 at 11:20
• No, it's not the same. KMP pi(i) function computes the longest prefix that is also a suffix of the substring S[0....i]. As stated in the question, given phi(w), we need to find the longest prefix of S that is also a prefix of the substring that starts at S[w]. Feb 21, 2023 at 14:41

The algorithm you mentioned is correct. Note as the comments pointed out, that you want to compute the so called $$z$$-function: $$z[i] := \max_{k\in[n]}\{k\,|\, S[1:k] = S[i:i+k],\,\, 0\leq i+k \leq n\}$$ using the $$\pi$$ function: $$\pi[i] := \max_{k\in[n]}\{k\,|\, S[1:k] = S[i-k:i],\,\, 0\leq i-k \leq n\}$$ We claim that $$z[i] := \max_{k\in[n]}\{k\,|\, \pi[i+k] = k,\,\, 0\leq i+k\leq n\}$$ Notice for each $$i\in [n]$$: $$\pi[i+k] = k \iff S[1:k] = S[i:i+k]$$ By taking the maximum over $$k\in [n]$$ our proof is complete. This yields the algorithm:
z[1,...,n] = 0