Wednesday 31 December 2014

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')

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)


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