Problem Compressed String
Find the Compressed String [C Program]
You are given a collection of words, say as in a dictionary. You can represent it in the following compressed form: the first word will be followed by a sequence of a pair of number and a word. The number in the pair is the position till which the previous words' characters are included in the new word and the tail is the remaining trailing word which is the different than the previous word.
Example:
Suppose successive words in our dictionary are:
color
comma
commatose
dot
Then we can compress it in the following way:
color
2 mma (to denote that first two characters are same as that of 'color' and remaining string is 'mma')
Example:
Suppose successive words in our dictionary are:
color
comma
commatose
dot
Then we can compress it in the following way:
color
2 mma (to denote that first two characters are same as that of 'color' and remaining string is 'mma')
5 tose (to denote that the first five characters are same as that of 'comma' and remaining string is 'tose')
0 dot (to denote that zero characters are same as that of 'commatose' and the remaining string is 'dot')
Input Format:
First line contains the integer 'n' denoting the number of words in the dictionary s.t. 1 <= n <= 1,000
Second line would contain the first word.
It will be followed by 'n-1' lines each containing an integer and a trailing string.
Note: The input is designed such that the integer will always be <= size of previous word formed
Example Input:
4
zebra
3 u
2 nith
1 ggurat
Output Format:
Output a single string that is the last resulting word of the given dictionary
Example Output:
zggurat
Explanation:
The dictionary actually is:
zebra
zebu (3 first characters are common with zebra)
zenith (2 first characters are common with zebu)
zggurat (1 first character is common with zenith)
zggurat
Explanation:
The dictionary actually is:
zebra
zebu (3 first characters are common with zebra)
zenith (2 first characters are common with zebu)
zggurat (1 first character is common with zenith)
Program:-
#include<stdio.h>
#include<string.h>
char *find(char st1[],char st2[],int in){
int i,j;
for(i=in,j=0;i<(in+strlen(st2));i++,j++){
st1[i]=st2[j];
}
st1[i]='\0';
return st1;
}
int main(){
int n,in;
scanf("%d",&n);
char str[n][20];
scanf("%s",str[0]);
for(int i=1;i<n;i++){
scanf("%d",&in);
scanf("%s",str[i]);
strcpy(str[0],find(str[0],str[i],in));
}
printf("%s",str[0]);
return 0;
}
-----------X-----------X-----------X-----------X-----------X----------
Input:-
3 cool 4 er 2 mmon-man
Output:-
common-man
0 Comments:
Post a Comment
Subscribe to Post Comments [Atom]
<< Home