Method to find Repeated pattern in String apart from Regex

Question

I would require to find a repeated pattern if it exists in a string or return a string in case repeated pattern does not exists.

Example:

String s = "abcabc"; Repeated pattern is abc
String s = "aba"; Repeated pattern is aba
String s = "abbbbbbba"; Repeated pattern is abbbbbbba;
String s ="abcdabcdabcd"; Repeated pattern is abcd;

If you refer to link we can solve this using regex Finding a repeated pattern in a string . But apart from regex is there some other way in which I can get it solved?

A loop that tests if the first character repeats, then tests if the first two characters repeat, etc.? What have you tried? — nnnnnn
– nnnnnn, Commented Sep 16, 2016 at 14:59

AnotherGeek · Accepted Answer · 2016-09-16 16:25:06Z

1

If there is a pattern => its length must divide the string length

for (int i =2;i < sqrt(length(s));i++)
{
   if(length(s) % i == 0)
{
 string pattern = s.substring(0,i);
 bool isPatern = true;
 int j = i +1;
 while(isPatern && j<length(s))
 {
    if(s.substring(j,i)==pattern)
     { 
        j = j+i;
     }
    else
     {
        isPatern  =false;
     }
 }
  if (isPattern) return pattern;
}

}

Note that this will return the smallest pattern, if you want the longest you do a for (int i =length(s)/2;i > sqrt(length(s));i--)

answered Sep 16, 2016 at 16:25

AnotherGeek

9041 gold badge6 silver badges28 bronze badges

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

Collectives™ on Stack Overflow

Method to find Repeated pattern in String apart from Regex

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related