I am unclear about the answer provided by Programming Pearls on the
question. What this does is to find longest string whose beginning is
separated by exactly M chars.
The original question is to find the longest string duplicated M
times. Any ideas on the approach for this? I could think of having a
suffix tree with each node keeping a count to keep track of "while
insertion how many times this node was passed while going down"
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
int pstrcmp(char **p, char **q)
{ return strcmp(*p, *q); }
int comlen(char *p, char *q)
{ int i = 0;
while (*p && (*p++ == *q++))
i++;
return i;
}
#define M 1
#define MAXN 5000000
char c[MAXN], *a[MAXN];
int main()
{ int i, ch, n = 0, maxi, maxlen = -1;
while ((ch = getchar()) != EOF) {
a[n] = &c[n];
c[n++] = ch;
}
c[n] = 0;
qsort(a, n, sizeof(char *), pstrcmp);
for (i = 0; i < n-M; i++)
if (comlen(a[i], a[i+M]) > maxlen) {
maxlen = comlen(a[i], a[i+M]);
maxi = i;
}
printf("%.*s\n", maxlen, a[maxi]);
return 0;
}
Best Regards
Ashish Goel
"Think positive and find fuel in failure"
+919985813081
+919966006652
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
