1

I want to determine an unknown pattern in a string such as,

s=112468112468112468112468112468.

So in this string, we can clearly see that 112468 is the repeating pattern. I searched on google quite a bit for finding some algorithms to help me, but I could only see ones which find a given pattern in a string such as Boyer-Moore algorithm etc.

What I do now to find these repeating unknown pattern is that,

for(i=0;i<Length of String;i++)
{
  for(j=i+1;j<Length of String;j++)
  {
    if(s[i]==s[j] && s[i+1]==s[j+1] && s[i+2]==s[j+2] && s[i+3]==s[j+3])
    {
       patternlength=j-i;

           for(k=i;k<j;k++)
           {
            pattern[k]=s[i+k]
           }
     }
   }
}

Although this works for the given string by using a comparison window of 4 literals, it may very well not work for some other string. Does anybody know a better solution to this.

Thanks

Fred Foo
  • 355,277
  • 75
  • 744
  • 836
Goku
  • 57
  • 6
  • 1
    Having a machine identify any patterns in text is not a trivial problem. Are you **only** interested in, for example, strings with repeating patterns? If you can give us the **type** or pattern or patterns for which you are interested in searching, we might be able to help more. – jefflunt Feb 20 '12 at 22:20
  • Well the kind of patterns I am dealing with will be strings with repeating patterns and would be very similar to the one I have written above as "s" and. The method which I have coded above works for me juss fine. But I just wanted to know if there is some standard algorithm for doing this. – Goku Feb 20 '12 at 22:26

1 Answers1

1

This is not pattern matching, this is pattern recognition, which is fundamentally different and potentially much harder.

However, the simple kind of pattern exhibited by this string could have been found using (Python code):

def find_repeated_pattern(s):
    for i in xrange(1, len(s) / 2):
        if s == s[:i] * (len(s) / i):
            return s[:i]

This is a naive implementation because of all its string copying, but it can be made to work in O(n²) time and constant space.

Fred Foo
  • 355,277
  • 75
  • 744
  • 836
  • 1
    Hi. Thanks for your reply. Actually the string in which I am supposed to find the pattern is also dynamically generated. I am not so much of a python expert but will this code snippet work for any kinda string ot is it specific to just like the code I have written. – Goku Feb 20 '12 at 23:12