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.
