You can use Suffix Arrays or Suffix Trees. On Mon, May 21, 2012 at 8:17 AM, Ashish Goel <ashg...@gmail.com> wrote:
> 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 > <jalaj.jaiswa...@gmail.com>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 <ashg...@gmail.com> 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 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. >>> >> >> >> >> -- >> 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 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. >> > > -- > 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. > -- *Thanks, Jeevitesh Shekhar Singh.* -- 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.