To find whether the given string is repetition of a substring

#include <stdio.h>
#include <string.h>

/*
Algo:
    Find the postion of the last character from the beginning

    if pos > mid return 0
    else
        rotationlength is the index of p and check whether the string satisfies the rotation with the rotation length
*/

int isPowStr(const char *str) {

int len = strlen(str);

const char *end = str + len - 1;

const char *mid = str + len / 2;


//find the postion of the last charater from the beginning
const char *p = strchr(str, *end);


//while the postion of the last character <= mid (no of repetitions >= 2)
while(p <= mid) {

int found = 1;
int rotlen = p - str + 1;
const char *s = p;

//check whether rotlen satiesfies
while(p >= str && found) {

const char *q = p + rotlen;

do{
if(*q != *p) {
found = 0;
break;
}

q += rotlen;

} while(q <= (end - (s - p))) ;

p--;
}

if(found)
return 1;

p = strchr(s + 1, *end);

}

return 0;
}


int main() {

char str[64];

scanf("%s", str);

printf("%d\n", isPowStr(str));

return 0;
}
Advertisements

One thought on “To find whether the given string is repetition of a substring

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s