For me, the easiest way to accomplish this is to have a "reader" index
and a "writer" index. At each iteration, increment the reader. If
the character at the position of the reader is NOT in the pattern,
then write that character to the writer position and increment the
writer.
i.e.
int len=strlen(subject);
int writer=0, reader=0;
while (reader < len) {
if (subject[reader] "not in pattern") {
subject[writer]=subject[reader];
writer++;
}
reader++;
}
The interesting part, to me, is how to implement "not in pattern." In
this case, the alphabet is at most 256 characters. So one can create
an int array, where array[i] = 1 if (char)i is in the alphabet, and 0
ow.
i.e.
int *p_array = (int*)calloc(256,sizeof(int));
int p_len = strlen(pattern);
int i;
for (i=0; i<p_len; i++) {
p_array[ (int)(pattern[i]) ]=1;
}
to implement "not in pattern" you just check
p_array[ subject[ reader ] ]. This approach takes O(n + c) where
n=len of subject and c is the size of the alphabet (a constant).
If you are not allowed to allocate more memory (or the alphabet is too
big), then sort pattern, so that you can do a binary search to
implement "not in pattern." This approach takes O(n *log(m)), where
n=len of subject and m=len of pattern. If you don't have a sorting
routine, and don't feel like writing one, then implement the "not in
pattern" via a sequential search of the pattern, for a O(n*m) running
time.
Another approach is to use a hash table...
Joe
On Aug 8, 10:11 am, "Manish Garg" <[EMAIL PROTECTED]> wrote:
> i think there is only one and srtaight forwad way to do this...
>
> i m writing C code for that.....if any one can do it with less
> complexity....plz reply..
>
> int flag;
> do{
> flag=0;
> for(int i =0;subject[i] !='\0';i++)
> {
> if(subjcet[i]==pattern[0]){
> for(int
> j=i,k=1;pattern[k]!='\0'&&subject[j]==pattern[k];j++,k++);
> if(pattern[k]=='\0'){
> while(subject[i+k]!='\0')
>
> subject[i]=subject[i+k];
> break;
> flag=1;
> }
> }
> }while(flag==1);
>
> On 8/8/07, Arulanandan P <[EMAIL PROTECTED]> wrote:
>
>
>
>
>
> > This was asked to me in Microsoft interview
>
> > On 8/7/07, Abhi <[EMAIL PROTECTED]> wrote:
>
> > > Is this your college assignment?
>
> > > On Aug 7, 9:00 pm, "Arulanandan P" <[EMAIL PROTECTED]> wrote:
> > > > You have to write a function whose prototype is given bellow. this
> > > function
> > > > will accept two char * named subject and pattern. for example
> > > > subject="abracadbra"
> > > > and pattern="bca".now it should check occurrences of all chars of
> > > string
> > > > pattern in subject . If any match occurs then it will remove that char
> > > from
> > > > subject . so finally , as in our example
> > > > at end subject ="rdr"
>
> > > > void fun(char *subject,char *pattern)
> > > > {
> > > > // write your code here}
>
> --
> With Best Regards...
> ---------------------
> Manish
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
