minimal cyclic sub string in a bigger cyclic string

Question

I am trying to find an algorithm that culd return the length of the shortest cyclic sub string in a larger cyclic string.

A cyclic string would be defined as a concatenation of tow or more identicle strings, e.g. "abababab", or "aaaa"...

Now in a given for example a string T = "abbcabbcabbcabbc" there is a cycle of the pattern "abbc" but the shortest cyclic sub string would be "bb".

Answer 1

If you're just looking for a substring that appears more than once:

Build a Suffix tree from the string.

While creating the suffix tree, you can count re-occurrences of every substring and save it on the number of occurrences on the node.

Then just do a BFS search on the tree (which will give you a layered search, from shorter to longer strings) and find the first substring which is longer than 1 that occurred more than once.

Total complexity: O(n) where n is the length of the string

Edit:

The paths from the root to the leaves have a one-to-one relationship with the suffixes of S

You can implement the tree that each node contains one letter, that will give you better granularity and allow you to see all the substrings by length.

Here's a suffix tree of banana where every node contains one letter, you can see that you have all the substrings there.

If you'll look at the applications section of the suffix tree, you'll see that it is used for exactly this kind of tasks - finding stuff about substrings.

Look at the image from the root, you can see ALL the substrings start from the root (BFS list):

b
a
n
ba
an
na
ban
ana
nan
bana
anan
nana
banan
anana
banana