Print out all possible sizes of subsequences of string in C

Question

For example, given a string "abcdefghijk", I want my function to print out:

a, b, c, d, e, f, g, h, i, j, k.
ab, bc, cd, de, ef, fg, gh, hi, ij, jk
abc, bcd, cde, def, efg, fgh, ghi, hij, ijk
abcd, bcde

I'm sure there's a better way to do this than what I currently have. What are some optimizations I could do? Mostly in terms of speed performance, but any kind of optimization would be great; time, space, design, etc...

The commas don't matter much, it's the order that I worry about at this point, so that a, b, b, c, c, d, d, e, e, f, f, g, g, h, h, i, i, j, j, k is fine for the second line.

int main(int argc, char const *argv[])
{
 char* s = "abcdefghijk";
 int n = 11;
 for (int k = 0; k < n; k++)
 {
 for (int i = 0; i < n-k; i++)
 { 
 for (int j = i; j <= i+k; j++)
 printf("%c, ",s[j]);
 }
 printf("\n");
 }
 return 0;
}

• JS1: The program doesn't do what you said it should. Instead of ab, bc, cd ... it prints a, b, b, c, c, d, ... for the second line.
• jeremy radcliff: @JS1, thanks I edited my question. I wasn't precise enough with the commas but what I'm trying to work out is really the order of the printing.
• 200_success: Your title says "subsequences", but your code and your examples are all substrings.

Answer 1

Here's a way that (at least IMO) at least marginally cleaner:

#include <stdio.h>
int main(int argc, char const *argv[])
{
 char s[] = "abcdefghijk";
 int n = sizeof(s);
 for (int k = 1; k < n; k++)
 {
 for (int i = 0; i < n - k; i++)
 {
 printf("%*.*s, ", k, k, s + i);
 }
 printf("\n");
 }
 return 0;
}

As to things about the code that can be improved, the most obvious would be using sizeof (or strlen, if necessary) to find the length of the input array, instead of hard-coding it.

Realistically, there's probably not a lot you can do to improve speed/performance--it's virtually guaranteed to be heavily I/O bound (though Tom Ernack's suggestion of using fwrite instead of printf might help--then again, depending on the standard library you're using, it might not).

Answer 2

I can't say if this will be a good optimization in terms of speed, but this will take out your inner for-loop and will at the same time resolve the issue with commas to make it look more like what you intended in your question:

int main(int argc, char const *argv[])
{
 char* s = "abcdefghijk";
 int n = 11;
 for (int k = 0; k < n; k++)
 {
 for (int i = 0; i < n-k; i++)
 { 
 fwrite(s + i, 1, k, stdout);
 printf(", ");
 }
 printf("\n");
 }
 return 0;
}

The idea is to let fwrite do the iteration over the characters in the string for you. A minor nitpick: initial declaration of the counters in the for (;;) loop is a C99 feature. I had to compile with -std=c99 to remove the error.

EDIT: Ah someone beat me to it while I was typing... I thought of using the precision specifier in printf but didn't know how to make it variable instead of a hardcoded constant.

• Quuxplusone: Re the implied advice to avoid "C99 features": There are college freshmen today who were not even alive in 1999. :)

Answer 3

One thing that I think is very important but not yet addressed in the other answers is: naming and abstraction.

Albeit your code is short, I have to look at it and think about what these loops are doing to understand what your code is supposed to do. It's much better if that's directly apparent from the identifiers (variable and function names). Speaking of functions, there's at least one functionality that I'd put into a separate function: printing a substring.

void print_substring (char const * from, char const * to) {
 fwrite(from, 1, to - from, stdout);
 // One could check return value to ensure
 // that all characters have been written,
 // but then you also need to decide what
 // to do in the case of an error.
}

Further, i, j and k are good names for generic loop counters, but here we can be way more specific:

// Note: prints all except the empty substring
void print_all_substrings(char const * string) {
 size_t const string_length = strlen(string);
 for (size_t substring_length = 1;
 substring_length <= string_length;
 ++substring_length) {
 char const * const last_begin = string + (string_length - substring_length);
 char const * begin = string;
 for (; begin != last_begin; ++begin) {
 print_substring(begin, begin + substring_length);
 printf(", ");
 }
 print_substring(last_begin, last_begin + substring_length);
 printf("\n");
 }
}

(Ideone test code)

• Quuxplusone: FWIW, I find the original code much easier to read than your rewrite. To take the most egregious example, for (int i = 0; i < n - k; ++i) is much easier on the eyes than your three-line version that begins char const * const last_begin = string + (string_length - substring_length);.
• Daniel Jour: @Quuxplusone In the original version you need to think about what the code could be doing. Mine is almost an description of the algorithm in plain English. No mental code execution necessary. True, it's much longer, though the example you point out is mostly due to me using pointers instead of indices. Take the original code and rename the variables accordingly. (Also I need to break it down to more lines because that's easier to deal with on a small mobile phone screen)
• Lundin: Abstraction is not necessarily a good thing. This is a perfect example of meta programming going out of control, transforming something utterly basic into something needlessly complex. I can look at the original code for 10 seconds and tell what it does. This code, I will have to stare at for 10 minutes. During which I'll get too annoyed at the subjective use/abuse of const correctness and stop reading...