How to check if string has repeating pattern?

For what it's worth I found a solution using regex.

The trick is to use the back-reference on a non-empty first group.

^(.+)(?:\1)+$

And as @PatrickParker points out, if you need the smallest repeating pattern then you can use a lazy qualifier

^(.+?)(?:\1)+$

private boolean checkPatternRepeatition(String s) {
    int secondMatch = (s + s).indexOf(s,1);
    return secondMatch < s.length();
}

Whenever there is a pattern repetition present in the string, concatenating them and searching for the pattern will result in a index that is less than the length of the string itself. If not it will return the length of the string. This takes O(M^2) time complexity as the indexOf() time complexity is O(M*N) where M - Length of the string and N - Length of the pattern.

Create Trie with all the sub strings at any location. While adding if you end up adding one word twice that is the word has been added previously, it means it has repeating pattern.

If you want pattern grater than any length, change your code to store only words grater than that length. Or a single character can also be a repeating pattern.

I don't know RegEx so I will do it a different way. And this only applies if the String is not a partial repeating string i.e. "xbcabbaabbaabbaxx"

First, you take the input string, and find the factors of the string size. A prime number will mean that there are no repeating patterns, as a repeating pattern implies a multiple of at least 2 of the pattern String length.

Thanks to Tot Zam: Finding factors of a given integer

public ArrayList<Integer> findFactors(int num) {        
    ArrayList<Integer> factors = new ArrayList<Integer>();

    // Skip two if the number is odd
    int incrementer = num % 2 == 0 ? 1 : 2;

    for (int i = 1; i <= Math.sqrt(num); i += incrementer) {

        // If there is no remainder, then the number is a factor.
        if (num % i == 0) {
            factors.add(i);

            // Skip duplicates
            if (i != num / i) {
                factors.add(num / i);
            }

        }
    }

    // Sort the list of factors
    Collections.sort(factors);

    return factors;
}

Once you find the factors of the number, in your case 16 (result being 1,2,4,8,16), and excluding the largest factor (which is itself), you can now create a loop and iterate on substrings of the string. You check for each value against its previous value, and check until you get a correct value using continue

For example, a rough sketch:

boolean isRepeatingPattern = false;
for (Integer factor : factors) {
    int iterations = stringSize / factor;
    String previousSubstring = stringParam.substring(0, factor); 
    for (int i = 1; i < iterations; i++) {
        int index = i * factor;
        if (previousSubstring != stringParam.substring(index, index + factor)) break;
        if (i == iterations - 1) repeatingPattern = true;
    }
}

I realize this post is a little dated, but it came up at the top of a google search on this topic, and since none of the answers provided what I needed, I ended up making a method that did and I simply wanted to add it to this post for future searchers.

This method produces the pattern or patterns that were found and the number of times each pattern repeats in the original string.

When I tried @flakes regex using string.matches(), it only matched true if the patterns were side by side. So it would match 101101 but not 101234101 (it didn't seem to know that the pattern 101 was in there twice.

So, if you simply need to know if your string has the same pattern in it side by side, use this code:

if (myString.matches("^(.+?)(?:\\1)+$")) {
  //doSomethingHere
}

Taking the idea of building a substring of patterns to the nth degree, I came up with this method, which basically builds a list of all possible patterns. Then it iterates through that list and checks the original string to see if that pattern is in it. Obviously it will ignore the first hit in the comparison since the pattern will always hit true one time in the source string ... on account of the pattern being created from the source string.

Here is the code, obviously you can massage it for your needs:

private void checkForPattern(String userString) {
    String               buildString;
    LinkedList<String>   patterns    = new LinkedList<>();
    int                  size        = userString.length();
    int                  hits;
    int                  newSize;
    String[]             coreString  = new String[size];
    Map<String, Integer> hitCountMap = new HashMap<>();

    for (int x = 0; x < size; x++) {
        coreString[x] = userString.substring(x, x + 1);
    }

    for (int index = 0; index < size - 1; index++) {
        buildString = coreString[index];
        for (int x = index + 1; x < size; x++) {
            buildString = buildString + coreString[x];
            patterns.add(buildString);
        }
    }

    for (String pattern : patterns) {
        String check = userString.replaceFirst(pattern, "");
        if (check.contains(pattern)) {
            newSize = userString.replaceAll(pattern, "").length();
            hits    = (size - newSize) / pattern.length();
            hitCountMap.put(pattern, hits);
        }
    }

    for (String pattern : hitCountMap.keySet()) {
        System.out.println("Pattern: " + pattern +
                           " repeated " + hitCountMap.get(pattern) +
                           " times.");
    }
}

Use this one line solution

private boolean checkPattern(String input) {
    return ((input + input).indexOf(input, 1) != input.length());

}

If a string of length abcabc is constructed by repeating substring abc, then abcabcabcabc. So if we ignore the very first occurrence of the subtring abc which starts from index 0, then we can see that the resulting string starting from the second occurrence of the substring abc. However, if it is not constructed from the repeating substrings, the first re-occurence will only start from the beginning of second string.

You could take the substring in another variable and run a loop for the initial string comparing for the first element of the substring

If it matches run if condition for the substring.

If any of the preceeding characters in the substring do not match, exit the substring's if condition

You can use String split method to get the repeating pattern.

public static String getRepeatingPattern(String str) {
    String repeatingPattern =null;
    for(int i=0;i<str.length();i++) {
        repeatingPattern = str.substring(0, i+1);
        String[] ary = str.split(repeatingPattern);
        if(ary.length==0) {
            break;
        }
    }
 return repeatingPattern;
}