WORDSTEM

• Problem Description

  
  Given n words w[1..n], which originate from the same stem (e.g. grace, graceful, disgraceful, gracefully), we are interested in the original stem. To simplify the problem, we define the stem as the longest consecutive substring that occurs in all the n words. If there are ties, we will choose the smallest one in the alphabetical (lexicographic) order. 
  

• Test Case 1

  
  Input (stdin)

  1
  
  4
  
  grace graceful disgraceful gracefully
  
  

  Expected Output

  grace

• CODING ARENA

• #include <stdio.h>

  #include<string.h>

  int main()

  {

    int i,j,k,l,m,n,o,p,t,len[15],flag,s,z,key,min;

    char a[15][25],ans[25],aa[25];

    scanf("%d",&t);

    for(z=1;z<=t;z++)

    {

      flag=s=0;

      min=1000;

      for(i=0;i<=24;i++)

      {

        ans[i]='\0';

      }

      scanf("%d",&n);

      for(i=0;i<=n-1;i++)

      {

        scanf("%s",a[i]);

        m=strlen(a[i]);

        len[i]=m;

        if(m<min)

        {

          min=m;

          key=i;

        }

      }

      for(i=min;i>=1;i--)

      {

        for(j=0;j<=min-i;j++)

        {

          l=j;

          k=0;

          while(k<=i-1)

          {

            aa[k]=a[key][l];

            k++;

            l++;

          }

          aa[k]='\0';

          for(o=0;o<=n-1;o++)

          {

            flag=0;

            for(p=0;p<=len[o]-i;p++)

            {

              if(strcmp(&a[o][p],aa)==a[o][p+i])

              {

                flag=1;

                break;

              }

            }

            if(flag==0)

              break;

          }

          if(flag==1)

          {

            s=1;

            if(strlen(ans)==0)

            {

              strcpy(ans,aa);

            }

            else

            {

              if(strcmp(ans,aa)>0)

                strcpy(ans,aa);

            }

          }

        }

        if(s==1)

          break;

      }

      printf("%s\n",ans);

    }

    return 0;

  }

  
  

      

     

        

   

• Test Case 2

  
  Input (stdin)

  1
  
  2
  
  courageful courage
  
  

  Expected Output

  courage