mohangupta13
BAN USER- 0of 0 votes
Answerswrite a function which takes a string S and a pattern string P and an integer i , and returns the i'th occurrence of P in S.
- mohangupta13 in India for Kindle
example S = "abcabcefgabc " , P = "abc" , i =3 , ..returns 10| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm
using binary search strategy :
int first1(int * a , int low , int high ) {
if ( low > high )
return -1;
else if( low == high ) {
if(a[low] == 1)
return low;
else return -1;
}
else {
int mid = (low +high )/2;
if( a[mid] == a[mid+1] ){
if(a[mid] == 1)
return first1(a,low,mid);
else
return first1(a,mid+2,high);
}
else return (mid+1) ;
}
}
}
using binary search strategy :
int first1(int * a , int low , int high ) {
if ( low > high )
return -1;
else if( low == high ) {
if(a[low] == 1)
return low;
else return -1;
}
else {
int mid = (low +high )/2;
if( a[mid] == a[mid+1] ){
if(a[mid] == 1)
return first1(a,low,mid);
else
return first1(a,mid+2,high);
}
else return (mid+1) ;
}
}
}
using binary search strategy :
int first1(int * a , int low , int high ) {
if ( low > high )
return -1;
else if( low == high ) {
if(a[low] == 1)
return low;
else return -1;
}
else {
int mid = (low +high )/2;
if( a[mid] == a[mid+1] ){
if(a[mid] == 1)
return first1(a,low,mid);
else
return first1(a,mid+2,high);
}
else return (mid+1) ;
}
}
}
using suffix trees (no tweak needed ).
- mohangupta13 February 25, 2012Preprocessing - O(n)
Searching - O(|P|) --size of pattern
Space - O(n)
Total time = O( |T| + |P| )
..if the Text to be search in is very large , KMP can be used to save extra space needed for suffix tree , but
Preprocessing = O(|p|)
search-time = O(|T| + i*|P|) , where 'i' is for the 'i'th occurrence of P .
space = O(|p|) .
Total time = O ( |T| + (i+1) |P| )