Kevin wrote:
> Hi guys,
>
> How can we do this efficiently:
>
> Given a string S. Find all the sub-sequence strings that are of length
> K.
>
> For example, given "abcd", and lenght k = 3, we will have:
> abc,
> abd,
> acd,
> bcd.
/* Think recursively! */
void print_all_subsequences(char *s, int is, char *r, char ir)
{
if (ir < 0)
printf("%s\n", r);
else {
r[ir] = s[is];
print_all_subsequences(s, is - 1, r, ir - 1);
if (is > ir)
print_all_subsequences(s, is - 1, r, ir);
}
}
int main(void)
{
char r[1000];
char s[] = "abcd";
int len = sizeof s - 1;
int k = 3;
r[k] = '\0';
print_all_subsequences(s, len - 1, r, k - 1);
}
----------------------------
If you want a solution with an explicit stack, then remove recursion,
----------------------------
void print_all_subsequences(char *s, int is, char *r, char ir)
{
int iss[1000], i = 0;
call:
if (ir < 0)
printf("%s\n", r);
else {
r[ir--] = s[is];
iss[i++] = is--;
goto call;
rtn:
if (is > ir) {
--is;
goto call;
}
}
if (i > 0) {
is = iss[--i];
++ir;
goto rtn;
}
}
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
