cyclic repetitions in a string

Question

Not really sure if this is purely a maths question.. I am looking if there is a faster way to look for cyclic repetitions in an input string. Say for example the input string is abcabcdabcabcd, it has 2 repetitions of abcabcd.

public class CyclicSimilarity {
    public static void main(String[] args)
    {
        String S =
                 ("abcabcdabcabcd");
        int x = S.length();
        boolean foundAns = false;
        ArrayList<Integer> fact = new ArrayList<Integer>();
        for(int i=1; i<=x; i++)
        {
            if(x%i == 0)
                fact.add(i);
        }
        System.out.println("Factors are : "+fact.toString());

        for(int i=0; i<fact.size()-1; i++)
        {
            if(match(fact.get(i), 0, S))
            {
                System.out.println("Answer : "+S.length()/fact.get(i));
                foundAns = true;
                break;
            }
        }
        if(!foundAns)
            System.out.println("Answer : 1");
    }

    private static boolean match(Integer f, int i, String S) {
        boolean boolRet = false;
        if(S.substring(i, i+f).equalsIgnoreCase(S.substring(i+f, i+f+f)))
        {
            if(i+f+f == S.length())
                return true;
            boolRet = match(f,i+f,S);
            return boolRet;
        }
        else
            return false;
    }
}

Answer 1

It looks like you're trying to find the minimal period in a string $s$. This can be done in time $O(n)$, where $n$ is the length of $s$.

The method is simple: look for occurrences of $s$ in the string $s . s$, where "." denotes concatenation. The first occurrence is at position $0$, of course. If the second occurrence is at position $p$, then $p$ is precisely the minimal period of $s$.

To find occurrences of $s$ in $s . s$, you can use the KMP algorithm, which takes linear time. It may be the case that there's a function that implements KMP in your language of choice, so you won't have to implement it yourself. I don't recall if there's such a function in java. You could probably find that out on stackoverflow.

UPDATE: you can turn this into code quite quickly using java's builtin "indexOf" method, like this:

public class Period {
    public static void main(String[] args) {
        String s = "abcabcdabcabcd";

        String doubled = (s + s).substring(1);
        int period = 1 + doubled.indexOf(s);

        System.out.println("The repeating part is " + s.substring(0, period));
    }
}

Note that I remove the first character from $s . s$. This is in order to find the second occurrence of $s$ instead of the first one. So in real code you should ensure that $s$ is non-empty beforehand.

Also, I'm not sure that this is linear, because I don't think that indexOf implements KMP. But I think it should work fine in real-life examples, maybe even faster than an honest KMP implementation.