# Check whether a String has a repitition of its substring

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?

Think about how you can use KMP to solve this.

3 Likes

Thanks for the reply and also for adding something extra to my knowledgeâŚ

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.