soln pls Best Regards Ashish Goel "Think positive and find fuel in failure" +919985813081 +919966006652
On Sun, May 20, 2012 at 5:49 PM, jalaj jaiswal <[email protected]>wrote: > I can give you a dynamic programming approach in O(n^2) and O(n) space . > > On Tue, May 15, 2012 at 12:22 PM, Ashish Goel <[email protected]> wrote: > >> >> 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 [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?hl=en. >> > > > > -- > Regards, > > Jalaj Jaiswal > Software Developer, > Adobe Systems > +91-9019947895 > * > * > FACEBOOK <http://www.facebook.com/jalaj.jaiswal89> > LINKEDIN<http://www.linkedin.com/profile/view?id=34803280&trk=tab_pro> > > -- > 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?hl=en. > -- 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?hl=en.
