1
$\begingroup$

This is a question from CLRS book. (Chapter 32, string matching, the question is the problem for the whole chapter, it's in the end of the chapter)

Let $y^i$ denote the concatenation of string y with itself $i$ times. For example, $(ab)^{3}$ = $ababab$. We say that a string $x\in X$ has repetition factor $r$ if x = $y^{r}$ for some string $y\in X$ and some $r > 0$. Let $p(x)$ denote the largest $r$ such that $x$ has repetition factor $r$. Give an efficient algorithm that takes as input a pattern $P[1..m]$ and computes the value $p(P_i)$ for $i = 1, 2,\dots,m$. What is the running time of your algorithm?

I found an answer like this: First compute Prefix function (based on the prefix function from the book), so we return $π$. Then, Suppose that $π[i] = i −k$. If $k|i$, we know that $k$ is the length of the primitive root, so, the word has a repetition factor of $\frac{i}{k}$. We also know that there is no smaller repetition factor $i$. Now, suppose that we have $k$ not dividing $i$. We will show that we can only have the trivial repetition factor of 1. Suppose we had some repetition $y^{r} = \Pi$. Then, we know that $π[i] ≥ y^{r}−1$. However, if we have it strictly greater than this, this means that we can write the $y$’s themselves as powers because we have them aligning with themselves.

COMPUTE-PREFIX-FUNCTION (P)
1 m = P.length
2 let π be a new array
3 π[1]= 0
4 k = 0
5 for q = 2 to m
6    while k > 0 and P[k+1] != P[q]
7       k = π[q]
8    if  P[k+1] != P[q]
9       k = k + 1
10   π[q] = k
11 return π

The prefix function is a part of KMP algorithm

KMP-MATCHER (T,P)
1 n= T.length
2 m =P.length
3 π=COMPUTE-PREFIX-FUNCTION (P)
4 q= 0 // number of characters matched
5 for i = 1 to n // scan the text from left to right
6    while q > 0 and P[q+1] != T[i]
7        q= π[q] // next character does not match
8    if P[q+1] == T[i+1]
9        q = q + 1 // next character matches
10   if q == m // is all of P matched?
11       print “Pattern occurs with shift” i - m
12       q=π[q] // look for the next match

I can't still really understand completely the answer. Why should we suppose $k$ not dividing $i$? And the explanation for the case of $k$ not dividing $i$, the repetition factor is 1, is confusing to me.

$\endgroup$
5
  • $\begingroup$ Some details are missing here. What is $P_i$? Is it the prefix consisting of the first $i$ symbols? What is the Prefix function? What does it return? $\endgroup$ Oct 24 '19 at 7:08
  • $\begingroup$ @YuvalFilmus I have edited the post $\endgroup$
    – amV
    Oct 24 '19 at 7:53
  • $\begingroup$ It's still not clear what $P_i$ is, and what is the significance of $\pi$ (what the function computes). $\endgroup$ Oct 24 '19 at 7:53
  • $\begingroup$ @YuvalFilmus there's nothing missing. This is the whole question in the CLRS book. Pi is probably the input array of string, with i is the interation. π is also an array. π[i] is the length of longest proper prefix of the substring P[1...i] which is also a suffix of this substring. This is a part of KMP algorithm $\endgroup$
    – amV
    Oct 24 '19 at 7:59
  • $\begingroup$ You seem to be guessing about the meaning of $P_i$. But the CLRS question is about computing $p(P_i)$ for all $i$. Without knowing what $P_i$ is, it is impossible to solve the question. $\endgroup$ Oct 24 '19 at 8:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.