finding repeating patterns

[jbv]

Dar,

I came up to something similar... Here's a (very raw and quite slow) first approach
(it checks only groups of 6 to 20 chars) :

on mouseUp
  set cursor to watch
  lock screen
  put fld 1 into myST
  put "" into myL
  set the casesensitive to true
  repeat with k=1 to 1000
    repeat with i=20 down to 6
      put k+i-1 into b
      get char k to b of myST
      put myST into a
      replace it with "" in a
      put ((number of chars of myST - number of chars of a) / b) into c
      if c>=2 then
        put it & tab & c & cr after myL
        exit repeat
      end if
    end repeat
  end repeat
  put myL
end mouseUp

> On Aug 26, 2006, at 3:17 PM, jbv wrote:
>
> > Does anyone have (or know of) an algorithm to find repeating
> > patterns of characters in a string ?
>
> This brute-force method came to my mind.  Decide on a min and max
> length of patterns.  Try all possible substrings.  (Outer loop is
> start position, inner loop is end char based on min & max length.
> With each one check in an array.  If not there put 1 otherwise
> increment.  Look for counts greater than 1.
>
> If the repeating pattern must come right after the starting pattern,
> then this does not apply.  In that case, just look for the repeats of
> the substring after the trial string.  The problem is that "xaxaxaxa"
> would be counted as a repeating of "xa" and a repeating of "xaxa".
>
> Dar Scott