Finding if a string is an iterative substring Algorithm in C?

I don't see that the KMP algorithm helps in this case. It is not a matter of determining where to begin the next match. It seems that one way to reduce the search time is to start with the longest possibility (half the length) and work downward. The only lengths that neeed to be tested are lengths that evenly divide into the total length. Here is an example in Ruby. I should add that I realize the question was tagged as C, but this was just a simple way to show the algorithm I was thinking about (and allowed me to test that it worked).

class String
def IsPattern( )
    len = self.length
    testlen = len / 2
    # the fastest is to start with two entries and work down
    while ( testlen > 0 )
        # if this is not an even divisor then it can't fit the pattern
        if ( len % testlen == 0 )
            # evenly divides, so it may match
            if ( self == self[0..testlen-1] * ( len / testlen ))
                return true
            end

        end
        testlen = testlen - 1
    end
    # must not have matched
    false
end
end

if __FILE__ == $0

   ARGV.each do |str|
       puts "%s, %s" % [str, str.IsPattern ? "true" : "false" ]
   end

end



[C:\test]ruby patterntest.rb a aa abab abcdabcd abcabcabc zzxzzxzzx abcd
a, false
aa, true
abab, true
abcdabcd, true
abcabcabc, true
zzxzzxzzx, true
abcd, false

You actually only need to care about testing substring lengths that are equal to the full string length divided by a prime number. The reason is: If S contains n copies of T, and n is not prime, then n = ab, and so S actually also contains a copies of bT (where "bT" means "T repeated b times"). This is an extension of anijhaw's answer.

int primes[] = { 2, 3, 5, 7, 11, 13, 17 };  /* There are one or two more... ;) */
int nPrimes = sizeof primes / sizeof primes[0];

/* Passing in the string length instead of assuming ASCIIZ strings means we
 * don't have to modify the string in-place or allocate memory for new copies
 * to handle recursion. */
int is_iterative(char *s, int len) {
    int i, j;
    for (i = 0; i < nPrimes && primes[i] < len; ++i) {
        if (len % primes[i] == 0) {
            int sublen = len / primes[i];
            /* Is it possible that s consists of repeats of length sublen? */
            for (j = sublen; j < len; j += sublen) {
                if (memcmp(s, s + j, sublen)) {
                    break;
                }
            }

            if (j == len) {
                /* All length-sublen substrings are equal.  We could stop here
                 * (meaning e.g. "abababab" will report a correct, but
                 * non-minimal repeated substring of length 4), but let's
                 * recurse to see if an even shorter repeated substring
                 * can be found. */
                return is_iterative(s, sublen);
            }
        }
    }

    return len;     /* Could not be broken into shorter, repeated substrings */
}

Notice that when recursing to find even shorter repeated substrings, we don't need to check the entire string again, just the first larger repeat -- since we've already established that the remaining large repeats are, well, repeats of the first one. :)

I can think of a heuristic, only call KMP on a sub string if Len(original string)/Len of(sub string) is a positive integer.

Also the maximum length of the sub string has to be less than N/2.

EDIT

Using these Heuristics Iwrote the follwing python code because my C is rusty at the moment

oldstr='ABCDABCD'    

for i in xrange(0,len(oldstr)/2):
       newslice=oldstr[0:i+1]
         if newslice*(len(oldstr)/len(newslice)) == oldstr:
             print 'pattern found', newslice
             break