# String matching problem needed some explanation

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.

• 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? Oct 24 '19 at 7:08
• @YuvalFilmus I have edited the post
– amV
Oct 24 '19 at 7:53
• It's still not clear what $P_i$ is, and what is the significance of $\pi$ (what the function computes). Oct 24 '19 at 7:53
• @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
– amV
Oct 24 '19 at 7:59
• 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. Oct 24 '19 at 8:07