In repeated substring patterns we have given a string check if it can be constructed by taking a substring of itself and appending multiple copies of the substring together.

Table of Contents

**Example**

Input 1: str = “abcabcabc” Output: True Explanation: “abcabcabc” can be formed by repeatedly appending “abc” to an empty string. Input 2: str = “xyxy” Output: True Explanation: “xyxy” can be formed by repeatedly appending “xy” to an empty string. Input 3: str = “xyzxy” Output: False Explanation: str has no such substring that can be repeatedly appended to an empty string to form str. Input 4: str = “Tutorialcup” Output: False

## Types of solution for repeated substring pattern

- KMP algorithm
- substring search

## KMP algorithm

### Approach for repeated substring pattern

We use the KMP algorithm to find the longest prefix *lps* which is also the suffix of the given string. If the length of the input string is some multiple *lps *and last character of the string matches with the last character of the *lps* string. Then we have a substring (which is lps itself) of the input string which when repeated (or appended) a certain number of times gives the input string itself.

We will construct an array dp[ ], where dp[i+1] stores length of the longest prefix which is also a suffix up to index i. After which we will check using dp[ ] if there exists any such substring of the input string.

To calculate dp[i], we are using values from dp[i-1 … 0], so this is a dynamic programming approach.

### Algorithm

- Construct an array dp[ ] of length = n+1, where n = string length. dp[i+1] denotes the length of the longest proper prefix of the string which is also a suffix up to the index = i.
- initiate two pointers j = 0 and i = 1, j is used to track the last character of the longest proper prefix,
**LPP**(also a suffix), i is used to tracking the current character during the traversal. - Begin traversing the string from left to right using i as the loop variable.
- if str[i] == str[j] => dp[++i] == ++j, if last character of
**LPP**and current character match, simply increase the length of LPP by 1. - Else if the characters don’t match:
- if length of LPP is 0 so far, then even first (str[0]) and current (str[i]) character don’t match => dp[i] = 0.
- if length of LPP is not 0, then simply recur => j = dp[j].

- After the traversal is over, return if the input string length is divisible by LPP length.

### Implementation

#### C++ Program

#include <iostream> #include <bits/stdc++.h> using namespace std; /* function that checks if the input string can be generated by repeatedly adding a substring of the input string */ bool hasRepeatedSubstring(string str) { int i = 1, j = 0, n = str.size(); /* dp[i+1] stores longest proper prefix upto index i which also a suffix */ vector <int> dp(n+1,0); /* Traverse the string */ while(i < n) { /* if the current character (at index = i) is same as the last character of longest common prefix obtained upto index i-1 */ if(str[i] == str[j]) dp[++i] = ++j; /* if characters don't match */ else { /* when str[0] and str[i] don't match no proper prefix which is also a suffix is possible so length is 0, simply move on to next character*/ if(j == 0) i++; /* decrease the length (by 1) of longest proper prefix (also suffix) possible upto index i-1 and then match the last character of longest proper prefix to character at current index */ else j = dp[j]; } } /* check if there is any such prefix of input string that has length that completely divides the input string length */ return dp[n] && (dp[n]%(n-dp[n]) == 0); } int main() { /* input string */ string str = "abcabcabc"; if(hasRepeatedSubstring(str)) cout<<"Formed by repeating substring"; else cout<<"Cannot be formed by repeated substring"; return 0; }

Formed by repeating substring

#### Java Program

import java.util.*; import java.io.*; class TutorialCup { /* function that checks if the input string can be generated by repeatedly adding a substring of the input string */ static boolean hasRepeatedSubstring(String str) { int i = 1, j = 0, n = str.length(); /* dp[i+1] stores longest proper prefix upto index i which also a suffix */ int [] dp = new int[n+1]; /* Traverse the string */ while(i < n) { /* if the current character (at index = i) is same as the last character of longest common prefix obtained upto index i-1 */ if(str.charAt(i) == str.charAt(j)) dp[++i] = ++j; /* if characters don't match */ else { /* when str[0] and str[i] don't match no proper prefix which is also a suffix is possible so length is 0, simply move on to next character*/ if(j == 0) i++; /* decrease the length (by 1) of longest proper prefix (also suffix) possible upto index i-1 and then match the last character of longest proper prefix to character at current index */ else j = dp[j]; } } /* check if there is any such prefix of input string that has length that completely divides the input string length */ return dp[n] != 0 && (dp[n]%(n-dp[n]) == 0); } public static void main (String[] args) { /* input string */ String str = "abcabcabc"; if(hasRepeatedSubstring(str)) System.out.print("Formed by repeating substring"); else System.out.print("Cannot be formed by repeated substring"); } }

Formed by repeating substring

### Complexity Analysis for repeated substring pattern

- Time Complexity: T(n) = O(n), single traversal of the input string is done.
- Space Complexity: A(n) = O(n), for the dp[ ] array used.

## Substring Search

### Approach for repeated substring pattern

If the original string has a repeating substring, the repeating substring can be no larger than 1/2 the length of the original string. Ex: “abcabc” would be “abc”.

By doubling the input string and removing the first and last character, i.e. “abcabcabcabc” => “bcabcabcab”, if the original string “abcabc” can be found in “bc**abcabc**ab”, it means that “abcabc” is made up by repeating one of its a substring.

### Algorithm

- Construct a string
*pattern*adding the input string*str*twice. - Remove the first and last characters in the
*pattern.* - Find for
*str*in the*pattern,*if the match is found return True else return False.

### Implementation

#### C++ Program

#include <iostream> #include <bits/stdc++.h> using namespace std; /* function that checks if the input string can be generated by repeatedly adding a substring of the input string */ bool hasRepeatedSubstring(string str) { string pattern = str.substr(1) + str.substr(0,str.length()-1); return pattern.find(str) != string::npos; } int main() { /* input string */ string str = "abcabcabc"; if(hasRepeatedSubstring(str)) cout<<"Formed by repeating substring"; else cout<<"Cannot be formed by repeated substring"; return 0; }

Formed by repeating substring

#### Java Program

import java.util.*; import java.io.*; class TutorialCup { /* function that checks if the input string can be generated by repeatedly adding a substring of the input string */ static boolean hasRepeatedSubstring(String str) { int n = str.length(); String pattern = str.substring(1) + str.substring(0,n-1); return pattern.contains(str); } public static void main (String[] args) { /* input string */ String str = "abcabcabc"; if(hasRepeatedSubstring(str)) System.out.print("Formed by repeating substring"); else System.out.print("Cannot be formed by repeated substring"); } }

Formed by repeating substring

### Complexity Analysis for repeated substring pattern

- Time complexity: T(n) = O(n), for sub string search.
- Space Complexity: A(n) = O(n), for generating the
*pattern*string out of input string.