a linear solution.
- initialize an array of 26 (count for each character) with zeros.
- scan pattern array and toggle equivalent alphabet's occurance field
- scan subject string and skip occured alphabets
sample program:
alphabets_occurance[26]={0,0,0,...}
void fun(char *subject,char *pattern)
{
//toggle dirty alphabets occured in pattern string
for(int i =0;subject[i] !='\0';i++)
{
alphabets_occurance[subject[i] - 'a'] = 1;
}
//have two indexs to traverse the subject array and skip dirty alphabets
int curr_count=0,forward_count=0;
for(int i =0;pattern[i]!='\0';i++)
{
if(alphabets_occurance[pattern[forward_count] - 'a'] !=1)
{
//not a dirty alphabet - include in output
pattern[curr_count]=pattern[forward_count];
curr_count++;
}
forward_count++;
}
//terminate output string
pattern[curr_count]='\0';
}
costs time at o(strlen(pattern)+strlen(subject)) and mem 26 bytes..
On 8/12/07, Peeyush Bishnoi <[EMAIL PROTECTED]> wrote:
>
> One solution to this problem is that :
>
> char s[]="abracadbra";
> char p[]="bca";
> char temp[];
>
> 1. First Remove element b of array p from array s .
> Compare b of array p with with characters of array s .
> if b is not matched with characters of array s
> insert those characters of s into new temp array .
> continue this till s reaches '\0';
> now again reassign the reduced characters of temp array back into
> array s;
>
> continuously repeat the step 1 for another characters in p till p become
> or reaches '\0' ;
>
> finally you have an array which doesn't have characters which are there in
> p array;
>
>
> I think it only need an extra temporary array , but at each interation
> array size is getting reduced & as well no. of time to compare elements is
> also get reduced .
>
> If any one have questions please ask;
>
> Thank you ,
>
> ---
> Regards
> Peeyush Bishnoi
>
> On 8/7/07, 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
> > }
> >
> >
> >
>
>
> --
> ----
> Peeyush Bishnoi
> >
>
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
