Check whether a String has a repitition of its substring

general
, ,
1

For example, if I enter a string like abcdabcd, then it can be said that it repeats with abcd and if I enter abcdef, then it is non-repititive.
So how should I check?
Please help.

2

Think about how you can use KMP to solve this.

3 Likes
3

Brother, my implementation(pseudocode):-

char* longest_substring(char* str)
{
    char* istr = str;
    int checker=0;
    int countmax = 0;
    int maxl = 0;
    char* maxidx = str;
    while(*str != '\0')
    {
        if((checker & (1 << *str)))
        {
            if(maxl < countmax) {
                maxl=countmax;
                maxidx= str; 
            }
            checker=0;
            countmax=1; // include count of the duplicate
        }
        else {
            ++countmax;
        }
        checker |= (1 << *str);
        str++;
    }
    if(maxl < countmax) {
        maxl = countmax;
        maxidx = str;
    }
    char* start = maxidx-maxl;
    if(maxl != 0)     start[maxl] = '\0';
    return start;
}
 
void main()
{
    char* test = strdup("abcdbbnjkuiokklmnuuurstnvwabcd");
    char* str = longest_substring(test);
}

Explanation:-

In the above code, we just keep track of the max length of the currently found substring in maxl. We also maintain the ‘maxidx’ (pointer address)
We just track the max only when you get repetitions in the substring found till now
checker bit variable helps us in detecting the duplicate in a substring. We set it back to 0 when we are done with detecting duplicate in the first substring.
after everything is done, we just subtract the ‘maxidx’ with the substring length to get the start of the substring. Just place a NULL character in maxl location to get the perfect longest substring
NOTE that, the input string is destroyed!!.. It doesn’t use extra space either for replicating the string argument or for finding duplicates within the string.
We do traversal only once the whole string and the 2 condition checks gives O(2n) performance. All other operations would be negligibly constant.
If there is a case like,
‘abcdefghijkklmnopqrstu’
What will be the output of the code? If there are equal sized substrings, the function just gives the first found substring.
For more information refer here.

3 Likes
4

@topcoder_7 Dude your implementation? I found the same implementation with the explanation in this site->Longest Substring in String

2 Likes
5

Thanks for the reply and also for adding something extra to my knowledge…

6

While it might be unlikely that @topcoder_7 is the author of the blog (although there would be nothing wrong there), what do you gain here in pointing it out? :slight_smile: If he understands the above code and adapted it to its own needs than the code is “yours” in the sense he fully understands it…And it’s also under no copyright infringement law… It’s a thin line between what’s your code and “copied” code, but, truth is, your code is the one you understand and manage to use and adapt to suit your needs :slight_smile: Don’t so…forceful about it :slight_smile: We’re here to learn

4 Likes