Use bit array rather using array of size 26
On 9/15/07, Deva R <[EMAIL PROTECTED]> wrote:
>
>
>
> 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 algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
