0
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ If you construct a suffix tree/suffix array, does this become easy to solve? $\endgroup$
    – D.W.
    Feb 7, 2023 at 1:27
  • $\begingroup$ 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. $\endgroup$
    – Mikey
    Feb 7, 2023 at 1:32
  • $\begingroup$ You were asked to compute something called the z-function (cp-algorithms.com/string/z-function.html). $\endgroup$ Feb 7, 2023 at 20:21
  • $\begingroup$ Isn't this the function computed by KMP itself? can you explain how this is different? $\endgroup$ Feb 21, 2023 at 11:20
  • 1
    $\begingroup$ 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]. $\endgroup$
    – Mikey
    Feb 21, 2023 at 14:41

1 Answer 1

2
+50
$\begingroup$

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
for i in [n]:
    k = pi(i)
    z[i-k] = max(z[i-k],k)

as you already described.

$\endgroup$

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.