Return to Answer

It looks nice, and you got the right algorithm.

Still, there are problems and additional ideas:

1. The const-qualifier on the two functions return-value is ignored. Didn't your compiler warn?

2. Denoting the start of a string-slice by pointer to start of the whole string and offset into it is cumbersome and inefficient. Just give a pointer to the start of the slice.

3. You are playing Shlemiel The Painter with all four strlen()-calls in your loops. The compiler might be able to hoist it four you, or it might not.

   If it cannot, at least those in countSubstrings() are cheaper by some constant factor than the calls to a fixed getCounts(), and thus don't influence your codes big-oh.
   But those in getCounts() turn the function from linear to quadratic, and thus the algorithm from quadratic to cubic.

   What I don't get is why you ask for the strings length at all.
   Just substitute !s[n] for strlen(s) == n.

4. By the way, the problem is symmetric in its two arguments. That can be used.

And that was all I found.

static int getCounts(const char* a, const char* b) { int prev = 0; int curr = 0; int r = 0; for (; *a && *b; r += prev) { ++curr; if (*a++ != *b++) { prev = curr; curr = 0; } } return r; } static int manyCounts(const char* a, const char* b) { int r = 0; while (*a) r += getCounts(a++, b); return r; } int countSubstrings(const char * a, const char * b) { return !*a ? 0 : manyCounts(a + 1, b) + manyCounts(b, a); } 

It looks nice, and you got the right algorithm.

Still, there are problems and additional ideas:

1. The const-qualifier on the two functions return-value is ignored. Didn't your compiler warn?

2. Denoting the start of a string-slice by pointer to start of the whole string and offset into it is cumbersome and inefficient. Just give a pointer to the start of the slice.

3. You are playing Shlemiel The Painter with all four strlen()-calls in your loops. The compiler might be able to hoist it four you, or it might not.

   If it cannot, at least those in countSubstrings() are cheaper by some constant factor than the calls to a fixed getCounts(), and thus don't influence your codes big-oh.
   But those in getCounts() turn the function from linear to quadratic, and thus the algorithm from quadratic to cubic.

   What I don't get is why you ask for the strings length at all.
   Just substitute !s[n] for strlen(s) == n.

4. Either int is always big enough, and should be used throughout, or it isn't, and you have to play it safe by using size_t.

5. By the way, the problem is symmetric in its two arguments. That can be used.

And that was all I found.

static int getCounts(const char* a, const char* b) { int prev = 0; int curr = 0; int r = 0; for (; *a && *b; r += prev) { ++curr; if (*a++ != *b++) { prev = curr; curr = 0; } } return r; } static int manyCounts(const char* a, const char* b) { int r = 0; while (*a) r += getCounts(a++, b); return r; } int countSubstrings(const char * a, const char * b) { return !*a ? 0 : manyCounts(a + 1, b) + manyCounts(b, a); } 

It looks nice, and you got the right algorithm.

Still, there are problems:

1. The const-qualifier on the two functions return-value is ignored. Didn't your compiler warn?

2. Denoting the start of a string-slice by pointer to start of the whole string and offset into it is cumbersome and inefficient. Just give a pointer to the start of the slice.

3. You are playing Shlemiel The Painter with all four strlen()-calls in your loops. The compiler might be able to hoist it four you, or it might not.

   If it cannot, at least those in countSubstrings() are cheaper by some constant factor than the calls to a fixed getCounts(), and thus don't influence your codes big-oh.
   But those in getCounts() turn the function from linear to quadratic, and thus the algorithm from quadratic to cubic.

   What I don't get is why you ask for the strings length at all.
   Just substitute !s[n] for strlen(s) == n.

And that was all I found.

It looks nice, and you got the right algorithm.

Still, there are problems and additional ideas:

1. The const-qualifier on the two functions return-value is ignored. Didn't your compiler warn?

2. Denoting the start of a string-slice by pointer to start of the whole string and offset into it is cumbersome and inefficient. Just give a pointer to the start of the slice.

3. You are playing Shlemiel The Painter with all four strlen()-calls in your loops. The compiler might be able to hoist it four you, or it might not.

   If it cannot, at least those in countSubstrings() are cheaper by some constant factor than the calls to a fixed getCounts(), and thus don't influence your codes big-oh.
   But those in getCounts() turn the function from linear to quadratic, and thus the algorithm from quadratic to cubic.

   What I don't get is why you ask for the strings length at all.
   Just substitute !s[n] for strlen(s) == n.

4. By the way, the problem is symmetric in its two arguments. That can be used.

And that was all I found.

static int getCounts(const char* a, const char* b) { int prev = 0; int curr = 0; int r = 0; for (; *a && *b; r += prev) { ++curr; if (*a++ != *b++) { prev = curr; curr = 0; } } return r; } static int manyCounts(const char* a, const char* b) { int r = 0; while (*a) r += getCounts(a++, b); return r; } int countSubstrings(const char * a, const char * b) { return !*a ? 0 : manyCounts(a + 1, b) + manyCounts(b, a); } 

It looks nice, and you got the right algorithm.

Still, there are problems:

1. Denoting the start of a string-slice by pointer to start of the whole string and offset into it is cumbersome and inefficient. Just give a pointer to the start of the slice.

2. You are playing Shlemiel The Painter with all four strlen()-calls in your loops. The compiler might be able to hoist it four you, or it might not.

   If it cannot, at least those in countSubstrings() are cheaper by some constant factor than the calls to a fixed getCounts(), and thus don't influence your codes big-oh.
   But those in getCounts() turn the function from linear to quadratic, and thus the algorithm from quadratic to cubic.

   What I don't get is why you ask for the strings length at all.
   Just substitute !s[n] for strlen(s) == n.

And that was all I found.

It looks nice, and you got the right algorithm.

Still, there are problems:

1. The const-qualifier on the two functions return-value is ignored. Didn't your compiler warn?

2. Denoting the start of a string-slice by pointer to start of the whole string and offset into it is cumbersome and inefficient. Just give a pointer to the start of the slice.

3. You are playing Shlemiel The Painter with all four strlen()-calls in your loops. The compiler might be able to hoist it four you, or it might not.

   If it cannot, at least those in countSubstrings() are cheaper by some constant factor than the calls to a fixed getCounts(), and thus don't influence your codes big-oh.
   But those in getCounts() turn the function from linear to quadratic, and thus the algorithm from quadratic to cubic.

   What I don't get is why you ask for the strings length at all.
   Just substitute !s[n] for strlen(s) == n.

And that was all I found.