10887 - Concatenation of Languages

[brianfry713]

hpjhc, try reading line by line so your code can handle empty strings.

[sampad74]

I got TLE.Here is my code,please help me to make my program fast.Thanks in advance.

Code: Select all

#include<stdio.h>
#include<string.h>
int main(void)
{
    int t,i;
    scanf("%d",&t);
    for(i=1;i<=t;i++)
    {
        int m,n;
        scanf("%d %d",&m,&n);
        char a[m][20],b[n][20],c[m*n][40];
        char e[1];
        int j,k,l=0;
        gets(e);
        //for(j=0;j<m;j++) scanf("%s",a[j]);
        for(j=0;j<m;j++) gets(a[j]);
        //for(j=0;j<n;j++) scanf("%s",b[j]);
        for(j=0;j<n;j++) gets(b[j]);
        for(j=0;j<m;j++)
        {
            for(k=0;k<n;k++)
            {
                strcpy(c[l],a[j]);
                l++;
            }
        }
        //printf("\n%s %s %s\n",c[0],c[1],c[2]);
        l=0;
        for(j=0;j<m;j++)
        {
            for(k=0;k<n;k++)
            {
                strcat(c[l],b[k]);
                l++;
            }
        }
        //printf("\n%s %s %s %s %s %s\n",c[0],c[1],c[2],c[3],c[4],c[5]);
        int count=0;
        for(j=0;j<(m*n);j++)
        {
            for(k=(j+1);k<(m*n);k++)
            {
                if(!strcmp(c[j],c[k])) count++;
            }
        }
        //printf("\n%d\n",(m*n)-count);
        printf("Case %d: %d\n",i,(m*n)-count);
        //printf("\n%s %s %s\n",c[0],c[1],c[2]);
    }
    return 0;
}

[brianfry713]

Read this thread for ideas. What is the complexity of your code, is it O(M * M * N * N)?

[Zyaad Jaunnoo]

hpjhc, try reading line by line so your code can handle empty strings.

Do we really have empty strings in the input set?

The problem statement says that the strings are formed by lower case letters only (a to z).

You can assume that the strings are formed by lower case letters (‘a’ to ‘z’) only, that they are less than 10 characters long and that each string is presented in one line without any leading or trailing spaces.

Confused about this one.

[brianfry713]

Do we really have empty strings in the input set?

Yes