I think a better approach can be :- using suffix array.
Suffix array is an array data structure which stores all suffixes of the
input string, sorted in lexicographical order.
Now we need to consider that substring which is repeated m times.
Now since all the suffixes starting with same character are contiguous, we
can use the following logic :-
1:- iterate from left of suffix array till we get m suffixes having same
prefix
2:- update the longest prefix P found so far
3:- if at any time we get a new prefix , start from that current suffix
After we reach end , P contains the result if any string is repeated M
times otherwise NULL
Space Complexity :- O(N) , N is length of input string
Time Complexity :- Building the suffix array is N^2 LogN (Worst Case ) +
Finding_Substring - O(N)
On Tuesday, 15 May 2012 12:22:25 UTC+5:30, ashgoel 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 view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/569uLe79pdcJ.
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.
