Hi there,
I got a tough interview questions lately, and I would like to hear
your opinion:
An array of N chars is given
Write an efficient algorithm to find all the repeating substring with a
minimal size
of 2
f.e
ABCFABHYIFAB
sunstrings are:
"AB"
"FAB"
Any suggestions?
/* BEGIN new.c output */
The string is "ABCFABHYIFAB"
substring 1 is "AB"
substring 2 is "FAB"
substring 1, "AB", is at "ABCFABHYIFAB" + 0
ABCFABHYIFAB
substring 1, "AB", is at "ABCFABHYIFAB" + 4
ABHYIFAB
substring 1, "AB", is at "ABCFABHYIFAB" + 10
AB
substring 2, "FAB", is at "ABCFABHYIFAB" + 3
FABHYIFAB
substring 2, "FAB", is at "ABCFABHYIFAB" + 9
FAB
/* END new.c output */
/* BEGIN new.c */
#include<stdio.h>
#include<string.h>
#define STRING ABCFABHYIFAB
#define SUB_1 AB
#define SUB_2 FAB
#define str(s) # s
#define xstr(s) str(s)
int main(void)
{
char *ptr;
char *sun[] = {xstr(SUB_1), xstr(SUB_2)};
const char *const string = xstr(STRING);
unsigned n;
puts("/* BEGIN new.c output */\n");
puts("The string is \"" xstr(STRING) "\"");
puts("substring 1 is \"" xstr(SUB_1) "\"");
puts("substring 2 is \"" xstr(SUB_2) "\"\n");
for (n = 0; n != sizeof sun / sizeof *sun; ++n) {
ptr = strstr(string, sun[n]);
while (ptr != NULL) {
printf("substring %u, \"%s\", is at \"%s\" + %d\n",
n + 1, sun[n], string, (int)(ptr - string));
puts(ptr);
putchar('\n');
ptr = strstr(ptr + 1, sun[n]);
}
}
puts("/* END new.c output */");
return 0;
}
/* END new.c */