String self-similarity

It's a string problem I have been making on Hackerrank. It is executing fine on all test cases except the last two. These last two test case are declaring it "Terminated due to time out".

C programs are allowed 2 seconds on this site and somehow my program is taking a fraction beyond 2 seconds. How am I supposed to reduce that time taken?


For two strings A and B, we define the similarity
of the strings to be the length of the longest prefix common to both
strings. For example, the similarity of strings "abc" and "abd" is 2,
while the similarity of strings "aaa" and "aaab" is 3.


Calculate the sum of similarities of a string S with each of its suffixes.

#include
#include
void stringMatch(char strMain[]) {
        int similarity = 0,i,j;
        for(i =0;i<strlen(strMain);i++){
            for(j =0;j+i<strlen(strMain);j++){
                if(strMain[j] == strMain[j+i]){
                    similarity++;
                }else{
                    break;
                }

            }
        }
        printf("%d\n",similarity);
}

int main(){
        int T,i;
        scanf("%d",&T);
        char str[1000000];
        for(i =0;i<T;i++){
            scanf("%s",str);
            stringMatch(str);
        }
}

You re-calculate string length every iteration of every loop:

for(i =0;i<strlen(strMain);i++){
        for(j =0;j+i<strlen(strMain);j++){

It does not look like the string changes length. So calculate it once.

size_t  size = strlen(strMain);
    for(i =0; i < size; i++){
        for(j =0; j+i < size; j++){

Or don't even calculate it at all. The string is terminated when you reach the '\0' character so just look for that

for(i =0; strMain[i]; i++){
        for(j =0; strMain[j+i]; j++){

The other thing I noticed is that you are checking the string against itself. Which is not similar to the description you give above (where you are comparing two different strings).

StackExchange Code Review Q#54407, answer score: 5