Interested to Buy Any Domain ? << Click Here >> for more details...
Answer Posted / om
Input: str1 (size M), str2 (size N)
Output:- Union_string str3.
1. Take a auxillary interger array of size 128 and
initialize all its's enteries to zero.(becoz All printable
chacter has value in the range [0,127]. so 128)
int Aux[128]={0}; //O(128) TIME
2. set Couter = strlen(str1) + strlen(str2) +1 ;//extra one
for '\0' character..
3. now scan the first string str1 and put 1 on the index
value equal to str1[i] in auxillary array.If there were
already 1,then Counter--;
Aux[str1[i]]=1; //O(M) TIME
4. now scan the second string str2 and put 1 on the index
value equal to str2[i] in auxillary array.Similar to step 3.
If there were already 1,then Counter--;
Aux[str2[i]=1; //O(N) TIME
5. Now alloacte a memory of size equal to "Counter" for our
resulting union string str3.
char *str3=(char*)malloc(Counter);
6. now again scan the str1 followed by str2. and if any 1 is
found in Aux[str1[i]] or Aux[str2[i]] make it 0. and put
that character to union string str3.
int k=0;
for(int i=0; str1[i]!='\0' ;i++) //O(M)
if(Aux[str1[i]] ==1)
{
str3[k++]=str1[i];
Aux[str1[i]] =0;
}
for(int i=0; str2[i]!='\0' ;i++) //0(N)
if(Aux[str2[i]] ==1)
{
str3[k++]=str2[i];
Aux[str2[i]] =0;
}
str3[k]=\0';
and return str3.
// SO TOTAL O(MAX(M,N)) TIME COMPLEXITY ALGORITHM USING
CONSTANT SPACE OF SIZE 128.
| Is This Answer Correct ? | 2 Yes | 2 No |
Post New Answer View All Answers
What is the correct declaration of main?
Is fortran still used today?
What is the difference between pure virtual function and virtual function?
How can I call system when parameters (filenames, etc.) Of the executed command arent known until run time?
How can I pad a string to a known length?
Why is c used in embedded systems?
What is non linear data structure in c?
What is sizeof c?
what is the difference between north western polytechnique university and your applied colleges?? please give ur answers for this. :)
What is the difference between if else and switchstatement
write a c program to print the next of a particular no without using the arithmetic operator or looping statements?
What is the difference between a string and an array?
Write a program to check whether a number is prime or not using c?
What is the difference between ++a and a++?
I completed my B.tech (IT). Actually I want to develop virtual object that which will change software technology in the future. To develop virtual object what course I have to take. can I any professor to help me.
