CODEWITHSUNDEEP
regexstringalgorithm
user1242321
user1242321

Reputation: 1696

Find a Repeated Substring Pattern in a given string

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.

Upvotes: 4

Views: 6681

Answers (3)

Shikhar Johri
Shikhar Johri

Reputation: 41

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.

Upvotes: 0

Manish Chauhan
Manish Chauhan

Reputation: 175

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:

  1. str: abab. Repeat str: abababab. Remove the first and last characters: bababa. Check if abab is a substring of bababa.
  2. 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)

Upvotes: 10

MBo
MBo

Reputation: 80187

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)

Upvotes: 0

Related Questions