Re: [algogeeks] Print longest string duplicated M times
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.comwrote:
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 500
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
LINKEDINhttp://www.linkedin.com/profile/view?id=34803280trk=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.
Re: [algogeeks] Print longest string duplicated M times
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.comwrote:
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 500
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
LINKEDINhttp://www.linkedin.com/profile/view?id=34803280trk=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.
[algogeeks] Print longest string duplicated M times
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 500
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.
