String Unknown pattern Matching

Question

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

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
– jefflunt, Commented Feb 20, 2012 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
– Goku, Commented Feb 20, 2012 at 22:26

Fred Foo · Accepted Answer · 2012-02-20 22:29:16Z

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.

answered Feb 20, 2012 at 22:29

Fred Foo

365k80 gold badges765 silver badges852 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Goku Over a year ago

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.

Collectives™ on Stack Overflow

String Unknown pattern Matching

1 Answer 1

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related