6
\$\begingroup\$

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<stdio.h>
#include<string.h>
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);
        }
}
\$\endgroup\$
1
  • \$\begingroup\$ The errors have gone away, so this has been reopened. Please remember to include all code so that others can compile and run it. \$\endgroup\$
    – Jamal
    Jun 16, 2014 at 17:31

3 Answers 3

5
\$\begingroup\$

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).

\$\endgroup\$
2
  • \$\begingroup\$ still it dint work. taking 3 seconds. :( \$\endgroup\$
    – vaibhav
    Jun 16, 2014 at 17:49
  • \$\begingroup\$ Look at my newly posted solution.... it worked for me... i don't know why i got down votes though.... \$\endgroup\$
    – Debasis
    Jun 16, 2014 at 18:33
3
\$\begingroup\$

Your solution takes O(L3) time, where L is the length of the string. There are two levels of for-loops, each of which is O(L). However, you call strlen() repeatedly, and strlen() is O(L). You shouldn't need to call strlen() at all of you just look for the \0 terminator as you iterate. That would bring it down to O(L2).

However, what you really need is a smarter algorithm. As it happens, I reviewed just such an algorithm a few days ago, called the Z Algorithm, which returns an array of the lengths of self-similar prefixes. That should work in O(L) time and O(L) space.

\$\endgroup\$
-3
\$\begingroup\$

The problem with the slow running time is due to the presence of two loops in your code. In this particular case, only one suffices. The following code should be fast enough to pass your benchmarking test.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <assert.h>
/* Head ends here */

int commonPrefix(char* a, char* b) {
    char *x, *y;

    for (x = a, y = b; *x && *y; x++, y++) {
        if (*x != *y)
            break;
    }
    return x-a;
}

int stringSimilarity(char *a) {
    int len = strlen(a);
    char *suffix;
    int i, sum = 0;
    for (i = 1; i <= len; i++) {
        suffix = a + len-i;
        sum += commonPrefix(a, suffix);
    }
    return sum;
}

int main() {
    int res, t, i;
    scanf("%d",&t);
    char a[100001];
    for (i=0;i<t;i++) {
        scanf("%s",a);
        res=stringSimilarity(a);
        printf("%d\n",res);  
    }

    return 0;
}
\$\endgroup\$
4
  • 1
    \$\begingroup\$ Don't just dump your code here for the OP to use. Explain what you changed specifically and why the OP should change it to the way you have it. \$\endgroup\$
    – syb0rg
    Jun 16, 2014 at 22:02
  • \$\begingroup\$ In my previous code, I only wrote the commonPrefix function. I missed his question of addressing the self similarity, the function for which is now added in the new code. I've checked that the pasted code passes the Hackerrank test. \$\endgroup\$
    – Debasis
    Jun 16, 2014 at 22:35
  • 1
    \$\begingroup\$ The nested for-loops still exist. You've just hidden one of them inside a helper function, that's all. \$\endgroup\$ Jun 17, 2014 at 1:56
  • \$\begingroup\$ @Debasis Nopes, this solution isn't improving time. for the last 2 test cases it is taking 3 seconds. Same time my solution was taking. \$\endgroup\$
    – vaibhav
    Jun 17, 2014 at 3:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.