Re: [algogeeks] Re: Adobe Strings matching Puzzle.
Excuse the indentations, how about the following solution? O(strlen(B)).
match(char * A, char *B) {
char * tempA = *A;
while(1) {
char * tempB=*B;
while(*B *B == *A) {
*B++;*A++;
}
if(!*B)
return *tempB;
else {
while(*B *B++ != *A) ;
if(*B)
continue;
else
return NULL;
} //while(1)
}//match()
-Shiv
On Wed, Jul 28, 2010 at 3:41 AM, Anand anandut2...@gmail.com wrote:
It is just an Implementation of KMP string match Algorithm.
In the first section, I am find the prefix function π for a pattern which
encapsulates knowledge about how the pattern matches
against shifts of itself.
This information can be used in second section to avoid testing useless
shifts for string matching.
On Tue, Jul 27, 2010 at 3:41 AM, bujji jajalabu...@gmail.com wrote:
Hi Anand,
Can you please explain your code? What is the magic
number 10 in
if(k == 10)
{
printf(String Matched\n);
}
in your code?
What does while loop do in your code? Can you please write a comment?
-Thanks in advance,
Bujji
#include stdio.h
#include string.h
/* KMP algorithm for string Matching */
main()
{
char *p=This is my first post to this group;
char *T=to this group this is my post;
int len = strlen(p);
int len1 = strlen(T);
printf(len:%d len1:%d\n,len,len1);
int k = 0,i;
int
array[40]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
/* Pre processing which takes O(m)*/
for(i = 2; i len; i++)
{
while(k 0 p[k+1] != p[i])
{
k = array[k];
}
if(p[k+1] == p[i])
{
k++;
array[i] = k;
}
}
/* Matching which takes O(n) */
k = 1;
for(i = 0; i len1; i++)
{
while(k 0 p[k+1] != T[i])
{
k = array[k];
}
if(p[k+1] == T[i])
{
k++;
printf(%d %d %c\n,k,i,p[k]);
if(k == 10)
{
printf(String Matched\n);
}
}
}
}
On Jul 22, 9:22 pm, Anand anandut2...@gmail.com wrote:
http://codepad.org/grtqfF5f
Here is KMP code to solve the problem
On Thu, Jul 22, 2010 at 2:01 AM, Mallesh Kavuluri mallesh...@gmail.com
wrote:
Taking for granted that KMP algorithm searches for a given string of
length n in a string of length m in O(n+m) time,
How do we solve this puzzle in linear time?
On Thu, Jul 22, 2010 at 1:29 PM, sharad kumar
aryansmit3...@gmail.comwrote:
@all:pls make use of KMP algorithm...because knuth morris prat algor
On Wed, Jul 21, 2010 at 6:16 PM, anugrah anugrah.agra...@gmail.com
wrote:
Stack can be used to push the characters of the string A and then
popped off while scanning through the string B until there is a
difference in the character read from the string B and the one
popped
off from the stack..
On Jul 20, 4:40 pm, agnibha nath agni.fl...@gmail.com wrote:
You can try rabin-carp..
On Jul 20, 4:18 pm, mallesh mallesh...@gmail.com wrote:
We are given two strings. A and B.
First few letters of A match with Last letters of B. We have to
find
the longest match in linear time.
Example:
char * A =This is my first post to this group;
char *B= to this group this is my post;
Algorithm should return starting position of substring to this
group
in string A.
How do we do this?
-Thanks and regards,
Mallesh
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
algogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
yezhu malai vaasa venkataramana Govinda Govinda
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
algogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
algogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text -
- Show quoted text -
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send
Re: [algogeeks] Re: Adobe Strings matching Puzzle.
Ignore the last post.
match(char * A, char *B) {
char * tempA = *A;
while(1) {
char * tempB=*B;
while(*B *B == *A) {
*B++;
*A++;
}
if(!*B)
return *tempB;
else {
while(*B *B != *A){
*B++ ;
}
if(*B) {
*A = *tempA;
continue;
}
else
return NULL;
} //while(1)
}//match()
On Wed, Jul 28, 2010 at 1:32 PM, Shiv ... shivsinha2...@gmail.com wrote:
Excuse the indentations, how about the following solution? O(strlen(B)).
match(char * A, char *B) {
char * tempA = *A;
while(1) {
char * tempB=*B;
while(*B *B == *A) {
*B++;*A++;
}
if(!*B)
return *tempB;
else {
while(*B *B++ != *A) ;
if(*B)
continue;
else
return NULL;
} //while(1)
}//match()
-Shiv
On Wed, Jul 28, 2010 at 3:41 AM, Anand anandut2...@gmail.com wrote:
It is just an Implementation of KMP string match Algorithm.
In the first section, I am find the prefix function π for a pattern which
encapsulates knowledge about how the pattern matches
against shifts of itself.
This information can be used in second section to avoid testing useless
shifts for string matching.
On Tue, Jul 27, 2010 at 3:41 AM, bujji jajalabu...@gmail.com wrote:
Hi Anand,
Can you please explain your code? What is the magic
number 10 in
if(k == 10)
{
printf(String Matched\n);
}
in your code?
What does while loop do in your code? Can you please write a comment?
-Thanks in advance,
Bujji
#include stdio.h
#include string.h
/* KMP algorithm for string Matching */
main()
{
char *p=This is my first post to this group;
char *T=to this group this is my post;
int len = strlen(p);
int len1 = strlen(T);
printf(len:%d len1:%d\n,len,len1);
int k = 0,i;
int
array[40]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
/* Pre processing which takes O(m)*/
for(i = 2; i len; i++)
{
while(k 0 p[k+1] != p[i])
{
k = array[k];
}
if(p[k+1] == p[i])
{
k++;
array[i] = k;
}
}
/* Matching which takes O(n) */
k = 1;
for(i = 0; i len1; i++)
{
while(k 0 p[k+1] != T[i])
{
k = array[k];
}
if(p[k+1] == T[i])
{
k++;
printf(%d %d %c\n,k,i,p[k]);
if(k == 10)
{
printf(String Matched\n);
}
}
}
}
On Jul 22, 9:22 pm, Anand anandut2...@gmail.com wrote:
http://codepad.org/grtqfF5f
Here is KMP code to solve the problem
On Thu, Jul 22, 2010 at 2:01 AM, Mallesh Kavuluri
mallesh...@gmail.comwrote:
Taking for granted that KMP algorithm searches for a given string of
length n in a string of length m in O(n+m) time,
How do we solve this puzzle in linear time?
On Thu, Jul 22, 2010 at 1:29 PM, sharad kumar
aryansmit3...@gmail.comwrote:
@all:pls make use of KMP algorithm...because knuth morris prat algor
On Wed, Jul 21, 2010 at 6:16 PM, anugrah anugrah.agra...@gmail.com
wrote:
Stack can be used to push the characters of the string A and then
popped off while scanning through the string B until there is a
difference in the character read from the string B and the one
popped
off from the stack..
On Jul 20, 4:40 pm, agnibha nath agni.fl...@gmail.com wrote:
You can try rabin-carp..
On Jul 20, 4:18 pm, mallesh mallesh...@gmail.com wrote:
We are given two strings. A and B.
First few letters of A match with Last letters of B. We have to
find
the longest match in linear time.
Example:
char * A =This is my first post to this group;
char *B= to this group this is my post;
Algorithm should return starting position of substring to this
group
in string A.
How do we do this?
-Thanks and regards,
Mallesh
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
algogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
yezhu malai vaasa venkataramana Govinda Govinda
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
Re: [algogeeks] Re: a google question
I guess your solution would also be proved incorrect with the following,
Numbers in bold are the two arrays.
125 122 120 110 104 103 102 101
100 999897
130255 252 250 240 234 233 232 231 230
229 228 227
128 253 250 248 238 232 231 230 229 228
227 226 225
126 251 248 246 236 230 229 228 227 226
225 224 223
125 250 247 245 235 229 228 227 226 225
224 223 222
105 230 227 225 215 209 208 207 206 205
204 203 202
104229 226 224 214 208 207 206 205 204
203 202 201
103228 225 223 213 207 206 205 204 203
202 201 200
102227 224 222 212 206 205 204 203 202
201 200 199
101226 223 221 211 205 204 203 202 201
200 199 198
100 225 222 220 210 204 203 202 201 200
199 198 197
99 224 221 219 209 203 202 201 200 199
198 197 196
98 224 221 219 209 203 202 201 200 199
198 197 196
manish...
From: Varun Nagpal varun.nagp...@gmail.com
To: Algorithm Geeks algogeeks@googlegroups.com
Sent: Mon, 3 May, 2010 12:26:24 PM
Subject: Re: [algogeeks] Re: a google question
Guys no one commented on my solution? Any takes on it?
Anyways, below is my solution (in pseudo code)
Pre-condition: A and B are sequences of equal length and sorted in
descending order
Input: Sequences A[1..N] and B[1..N] of equal lengths(N)
Ouput: Sequence C[1..N] containing sorted sum of ordered pairs from
cartesian products of A, B or B,A
Sort(A,B)
{
k = 1
N = length(A) = length(B)
C[1..2*N] = []// Empty array
cart_prod_order = 0 // 0 - AxB, 1 - BxA. 0 is default
// Complexity : O(N)
while(k != N+1)
{
if (A[k] B [k])
{
cart_prod_order = 1
break
}
else
{
k = k + 1
}
}
// Choose the correct order of Cartesian product sum
// Complexity: Theta(2N) = O(N)
if (cart_prod_order == 1)
{
// take cartesian product of B and A, storing the sum of ordered
pair (b,a) in each element of C
C[1..2N] = B[1..2] x A[1..N]
}
else
{
// take cartesian product of A and B, storing the sum of ordered
pair (a,b) in each element of C
C[1..2N] = A[1..2] x B[1..N]
}
// Merge
// C[1..N] and C[N+1..2N] are already sorted in descending order
// Complexity: Theta(N)
C[1..2N] = Merge(C[1..N],C[N+1..2N])
return C[1..N]
}
Merge(C,D)
{
i=1,j=1,k=1
E = []
while(i=length(C) OR j=length(D))
{
if(i=length(C) AND (jlength(D) OR C[i]D[j]))
{
E[k] = C[i]
i = i + 1
}
else
{
E[k] = D[j]
j = j + 1
}
k = k + 1
}
return E;
}
On Fri, Apr 30, 2010 at 7:50 PM, banu varun.nagp...@gmail.com wrote:
Nice question:
1. |A| = |B| i.e I assume their cardinality is equal
2. A(n) = { a1, a2 a3, ...aN} such that a1=a2=a3...=aN
3. B(n) = { b1, b2 b3, ...bN} such that b1=b2=b3...=bN
4. S(n^2) = A x B = {(a1,b1), (a1,b2)(a1,bN),
(a2,b1), (a2,b2)(a2,bN),
(aN,b1), (aN,b2)(aN,bN)}
assuming we have added in a way such that we find a pair ai bi,
for some i in 1..N such that a(i-1) = b(i-1)
A first observation is that in the worst case, the first 2N numbers in
S will contain the final result of N numbers.
i.e in (a1,b1), (a1,b2)(a1,bN), (a2,b1), (a2,b2)(a2,bN)
In the best case first N numbers in S will contain the final N numbers
(already sorted in decreasing order)
i.e in (a1,b1), (a1,b2)(a1,bN)
Now, if we consider again the worst case scenario, then we can first
divide 2N numbers in two groups of size N each and each of this group
is already sorted in decreasing order.
i.e (a1,b1), (a1,b2)(a1,bN) and (a2,b1), (a2,b2)(a2,bN)
Now we can simply apply Merge Algorithm on these 2 already sorted
arrays of size N each in O(N) time, which solves the problem
I can be wrong only if the the results lie outside first 2N
numbers(which I hope is not the case).
On Apr 30, 2:05 pm, divya sweetdivya@gmail.com wrote:
Given two sorted postive integer arrays A(n) and B(n) (W.L.O.G, let's
say they are decreasingly sorted), we define a set S = {(a,b) | a \in
A
and b \in B}. Obviously there are n^2 elements in S. The value of such
a pair is defined as Val(a,b) = a + b. Now we want to get the n pairs
from S with largest values. The tricky part is that we need an O(n)
algorithm.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this
[algogeeks] finding repeated substrings
Hi, Given a string, I am interested in finding all repeated substrings of any length (not just the longest substring). Can anybody point me to the right algorithm/literature for this problem? My original problem is finding repeated subtrees in a tree that has nodes of different kind. My plan is to convert the tree into a prefix notation and solve the above mentioned substring problem. Thanks Harsha -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Re: algorithm
How about keeping heap? Have two heaps 1. max heap and 2. min heap keep them equal size all the time and shift top element from one to other when required... On Wed, Jul 28, 2010 at 7:46 AM, Gene gene.ress...@gmail.com wrote: I think you have confused the statement of this problem. The (in sorted order) comment makes no sense because a median is exactly one number. One number is always sorted. After every stream element is read, you want to be able to get the median of all elements read so far. You're correct that the way to do this is maintain the elements in some kind of sorted data structure where you have O(1) access to the middle element. An array or list will work fine, but each stream element will require O(n) to insert in the sorted order (just as you'd do for insertion sort). It's easy to use a balanced tree instead. This reduces the processing time for each element to O(log n). You must maintain the invariant that the root of the tree is the median, so access time is still O(1). When a new element is read, it goes in either the left or right subtree of the root. This may cause the median to shift by 0 or 1 position in either direction. In this case, you'll always be able to pull the successor or predecessor of the root--whichever is the new median--up to the root by using e.g. AVL rotations. You'd have to prove that this does not make the tree too unbalanced so that the O(log n) insertion is hurt, but I don't think this would be hard. On Jul 24, 10:32 am, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote: You are given a stream of numbers which can be positive or negative. You are required to provide an operation FIND MEDIAN..which when invoked should be able return the median of the numbers in stream (in sorted order) in O(1) time. Eg: 0 1 2 3 4 Right FIND MEDIAN returns 2 as median Now input is -2 -4 So Stream = 0 1 2 3 -2 -2 -4 Sorted Stream would be -4 -2 0 1 2 3 4 and FIND MEDIAN returns 1 -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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 algoge...@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] On Complexity of Algorithm
A sorting algorithm takes 1 second to sort 1,000 items on your local machine. How long will it take to sort 10,000 items ... if you believe that the algorithm takes time roughly proportional to nlogn? [Show your calculations / logic to arive at an answer] -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Re: On Complexity of Algorithm
t = C * n log n, where C is the constant of proportionality, which will depend on the base of the logarithms used. (We can use any convenient base. I'll use base 10.) 1 = C * 1000 log 1000 so C = 1/3000. Then, when n = 10,000, t = 1 * log 1 / 3000 = 4/3000 = 13.3 sec. The algorithm will take about 13.3 seconds. Dave On Jul 28, 7:07 am, sourav souravs...@gmail.com wrote: A sorting algorithm takes 1 second to sort 1,000 items on your local machine. How long will it take to sort 10,000 items ... if you believe that the algorithm takes time roughly proportional to nlogn? [Show your calculations / logic to arive at an answer] -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] ALGORITHM
An array of unsorted numbers n is given with one no.repeated once ie n-1 distinct nos to find duplicate no. in o(n) complexity -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Re: ALGORITHM
@akshay Does the array contain numbers in the range 1 to n? On Jul 28, 8:16 pm, akshay akshayrastogi2...@gmail.com wrote: An array of unsorted numbers n is given with one no.repeated once ie n-1 distinct nos to find duplicate no. in o(n) complexity -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] ALGORITHM
What if the number are not consecutive? My approach- Put the numbers in a hash till a collision occurs. On Wed, Jul 28, 2010 at 9:21 PM, Apoorve Mohan apoorvemo...@gmail.comwrote: Solution : 1. Find Xor of numbers from 1 to n-1. 2. Find Xor of the numbers present in the array. 3. Xor the results from step 1 and 2 you will get the repeated number. On Wed, Jul 28, 2010 at 8:46 PM, akshay akshayrastogi2...@gmail.comwrote: An array of unsorted numbers n is given with one no.repeated once ie n-1 distinct nos to find duplicate no. in o(n) complexity -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards Apoorve Mohan -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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.
