Find a Repeated Substring Pattern in a given string

Question

Given a non-empty string check if it can be constructed by taking a substring of it and appending multiple copies of the substring together. You may assume the given string consists of lowercase English letters only and its length will not exceed 10000.

Example 1: Input: "abab"

Output: True

Explanation: It's the substring "ab" twice. Example 2: Input: "aba"

Output: False Example 3: Input: "abcabcabcabc"

Output: True

Explanation: It's the substring "abc" four times. (And the substring "abcabc" twice.)

I found the above question on a online programming site here. I submitted the following answer which is working for the custom test cases, but is getting time exceed exception on submission. I tried other way of regex pattern matching, but as expected, that should be taking more time than this way, and fails too.

public class Solution {
    public boolean repeatedSubstringPattern(String str) {
        int substringEndIndex = -1;
        int i = 0;
        char startOfString = str.charAt(0);
        i++;
        char ch;
        while(i < str.length()){
            if((ch=str.charAt(i)) != startOfString){
                //create a substring until the char at start of string is encountered 
                i++;
            }else{
                if(str.split(str.substring(0,i)).length == 0){
                    return true;
                }else{
                    //false alarm. continue matching.
                    i++;
                }
            }
        }
        return false;
    }
}

Any idea on where I am taking too much time.

Check this: (.+?)\1 Demo on Regex101: regex101.com/r/AiPdzC/3 — Mohammad Yusuf
– Mohammad Yusuf, Commented Nov 18, 2016 at 6:06

Julien M · Accepted Answer · 2020-09-04 03:36:21Z

Ther's a literally one-line solution to the problem. Repeat the given string twice and remove the first and last character of the newly created string, check if a given string is a substring of the newly created string.

def repeatedSubstringPattern(self, s: str) -> bool:
     return s in (s + s )[1: -1]

Eg:

str: abab. Repeat str: abababab. Remove the first and last characters: bababa. Check if abab is a substring of bababa.
str: aba. Repeat str: abaaba Remove first and last characters: baab. Check if aba is a substring of baab.

Mathematical Proof:

Let P be the pattern that is repeated K times in a string S.

S = P*K.

Let N be the newly created string by repeating string S

N = S+S.

Let F be the first character of string N and L be the last character of string N

N = ( F+ P*(K-1) )+ (P*(K-1) + L)

N = F+ P(2K-2)+ L

If K = 1. i.e a string repeated only once

N = F+L. //as N != S So False

If K ≥ 2.

N = F+k'+ N

Where k'≥K. As our S=P*K. So, S must be in N.

We can further use KMP algorithm to check if S is a sub-string of N. Which will give us time complexity of O(n)

MBo · Accepted Answer · 2016-11-18 06:45:59Z

0

You can use Z-algorithm

Given a string S of length n, the Z Algorithm produces an array Z where Z[i] is the length of the longest substring starting from S[i] which is also a prefix of S, i.e. the maximum k such that S[j] = S[i + j] for all 0 ≤ j < k. Note that Z[i] = 0 means that S[0] ≠ S[i]. For easier terminology, we will refer to substrings which are also a prefix as prefix-substrings.

Build Z-array for your string and find whether such position i exists for that i+ Z[i] = n and i is divisor of n (string length)

answered Nov 18, 2016 at 6:45

MBo

80.7k5 gold badges61 silver badges99 bronze badges

Comments

Shikhar Johri · Accepted Answer · 2020-09-07 17:38:59Z

0

A short and easily understandable logic would be:

def repeatedSubstringPattern(s: str):
    for i in range(1,int(len(s)/2)+1):
        if set(s.split(s[0:i])) == {''}:
            return True 
    return False

You can also write return i for return the number after which the pattern repeats itself.

answered Sep 7, 2020 at 17:38

Shikhar Johri

411 bronze badge

1 Comment

ryanwebjackson Over a year ago

It may not be self-explanatory to all. When does set(s.split(s[0:i])) == {''} return true?

Collectives™ on Stack Overflow

Find a Repeated Substring Pattern in a given string

3 Answers 3

Comments

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related