6
$\begingroup$

Let $\Sigma = \{ \sigma_1 , ..., \sigma_t \}$ and let $S$ be a string from $\Sigma^*$. Denote: $n=|S|$, that is $S$ has $n$ letters. I'd like to find the shortest prefix $T$ of $S$ such that $S$ is a prefix of $T^n$ ($T^n= T \cdot .... \cdot T$, $n$ times).

I tried to build the suffix tree for $S$, and then checking each node, by their levels - from lowest level to top level, because then the corresponding prefix will be shortest at the lowest level of the suffix tree and will get longer - and then for each node checking if this property applies for the prefix of the current suffix node I'm looking at, but that would not necessarily give me the shortest prefix, because the suffix tree may have on the same level different lengths suffices.

I'm not sure as to how I'll be able to find the shortest prefix $T$? Perhaps there is a different way of using a suffix tree?

Or maybe there is a way to solve this efficiently without using suffix trees at all?

$\endgroup$
  • 1
    $\begingroup$ Do you really assume that $|\Sigma| = |S| = n$? $\endgroup$ – J.-E. Pin Jan 24 '16 at 20:43
  • $\begingroup$ (I guess not using suffix trees includes not using suffix arrays.) $\endgroup$ – greybeard Feb 15 '16 at 22:52
  • 2
    $\begingroup$ If I am not mistaken, this is called the period of the string $S$. It can be computed using Knuth-Morris-Pratt. See also azam's answer and questions elsewhere. stackoverflow.com/questions/10515159/… $\endgroup$ – Hendrik Jan Feb 16 '16 at 15:06
1
$\begingroup$

Repetitions and periods in strings constitute one of the most fundamental areas of string combinatorics.1

The shortest prefix T of S where,

$S = T^k.Q , s.t: k>= 1, Q =$ some prefix of T, then |T| is called the period of string.

We say that string w has period p if w[i] = w[i + p] 1

Conventionally, finding T can be done by the Knuth–Morris–Pratt algorithm as well as Boyer–Moore string search algorithm.

Proving the correctness is beyond the scope of this answer.(More precisely, beyond my scope). See 1 for a better idea.


Before I came to know this, I attempted to solve this using KMP. And later, luckily, others have confirmed it. This could be helpful if one is wondering how could one possibly get an idea that KMP would work. I first tried to figure out the pattern and thought KMP could do the job.

Wondering how ? Our aim is to make $S$ a prefix of $T^n$ i.e. $TT \cdot .... \cdot T$, $n$ times. You can see that T is repeating itself, so, should some prefix of $S$ too.

E.g. take $S = abc$, the only way you can have $TTT$ and $S$ as a prefix of $TTT$ ($T^3$) is if $T = abc$, then $abc$ is a prefix of $abcabcabc$. The minimum part which is repeating is the complete string $abc$. Hence, $T = abc$.

But, if $S = aba$, then $T$ can be $ab$, and $aba$ is a prefix of $TTT$ i.e. $ababab$. The minimum part which is repeating is just the string $ab$. Hence, $T = ab$.

You're roughly getting the idea that finding that part of prefix of $S$, where it is repeating itself in the rest of $S$ and ending with some part of it.

Final e.g. would be $S = abababa$, then again $T$ would remain $ab$, i.e, the prefix which is getting repeated and ending with some part of it. We could form $S$ as $T^k.Q: s.t. k >= 1, Q =$ some prefix of $T$, here $a$.

Now your job is pretty easy. For every prefix in $S$, check if it is present in the rest of $S$ as described above. The shortest one you find would be the answer.

KMP has an essential part called "Prefix Function". Below is the code for the Prefix function in C / C++. When I ran it over a couple of strings S, I found good results.

void make_prefix_fun(char pat[], int a[], int m){
    // i is moving forward, and j is staying behind.
    a[0] = 0 ;
    for ( int i = 1, j = 0 ; i < m ; i++ ){
        while ( pat[j] != pat[i] && j > 0 )
            j = a[j-1];
        if ( pat[j] == pat[i] )
            j++;
        a[i] = j;
    }
}


Sample Cases:
aba
a b a 
0 0 1 
//  ^ T = S[1..(|S| - 1)]

adbashdbhabsjd
a d b a s h d b h a b s j d 
0 0 0 1 0 0 0 0 0 1 0 0 0 0 
// T is the complete S    ^


abcdabcda
a b c d a b c d a 
0 0 0 0 1 2 3 4 5 
//              ^. T = S[1..(|S| - 5)]
// Cool. Found something here.


abababababababababa
a b a b a b a b a b a b a b a b a b a 
0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 
// Cool. Found something here.              ^. T = S[1..(|S| - 17)]

abababababababababaaaa
a b a b a b a b a b a b a b a b a b a a a a 
0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1 1 1 
// Working exactly as expected.                   ^

Found a pattern? Yes, we do.

If you observe the array, after the first couple of consecutive 0s,

  • if we get the series, 1,2,3...x strictly upto the end, we can have our T = S[1..(|S| - x)] and the length of your required T is N - a[N] where N = |S|.

  • else T = entire string S.

The required T is the longest prefix of S, which is repeating itself in S, and S ends with some prefix of T or in other words T = S[1...|T|], where |T| is called the period of the string.


References:

1 - Repetitions in strings: algorithms and combinatorics, Crochemore et al.

Credits:

devnum, Mihai Calancea, Hendrik Jan.

$\endgroup$
  • $\begingroup$ In your last example, why did you have several $1$'s after the $17$? Then in this example which string is $T$ if so? $\endgroup$ – Eric_ Feb 22 '16 at 21:51
  • $\begingroup$ @Eric_ I request you to try out the function over a couple of sample cases of your choice. The several 1s signify, the overlap of last 'a' with the first 'a'. Here, as I said, we did not get the strict series 1, 2, 3..upto some number. Therefore, T becomes the entire string "S" or "abababababababababaaaa". To better understand how KMP works, I request you to watch some videos in Youtube, or follow some tutorials. $\endgroup$ – azam Feb 23 '16 at 1:44
  • $\begingroup$ Took a while, but I see now why this works and is correct. Thank you! $\endgroup$ – Eric_ Feb 23 '16 at 17:38
  • $\begingroup$ Actually, the bounty was given, but its ok. $\endgroup$ – Eric_ Feb 24 '16 at 7:37

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.