10679 - I Love Strings!!

[shikhorroy]

Continuously I am getting SE..........where is the problem?????

Code: Select all

#include<iostream>
#include<string>
#include<cstdio>
#include<cstdlib>
using namespace std;
#define pf printf
#define sf scanf
int main()
{
    int k, q;
    string S, sub_s;
    int found;
    sf("%d",&k);
    while(k--)
    {
        cin>>S;
        sf("%d",&q);
        while(q--)
        {
            cin>>sub_s;
            found = S.find(sub_s);
            if (found == string::npos)
                printf("n\n");
            else    printf("y\n");
        }
    }
    return 0;
}

[brianfry713]

See on uva.onlinejudge.org "Information on Submission Errors"

[shikhorroy]

Hmm...mmm...
but I think this is a server problem.

[sobhan_cp]

i got submission error too
what is the se ??

[brianfry713]

Information on Submission Errors http://uva.onlinejudge.org/index.php?op ... 1&Itemid=1

[ehsanulbigboss]

[lighted]

If you read this thread you would see that this problem can be solved by Aho-Corasick or suffix tree or hash function...

It seems the problem limits were changed. Now there are up to 1000 queries.
And with KMP you have to go through the text now up to 1000 times, and that is too much.
So it seems that now you have to use Aho-Corasick (with this algorithm it is sufficient to go through the text once for a given set of patterns).

Now I think that this question is not very meaningful... It's like nearly impossible to be solved without a good algorithm book at home...

However i solved this problem without good algorithm book. 2 simple hash functions was enough to get accepted this problem in 1.745s.

For each string T i precalculate values of 2 hash functions where len is length of string T.

First hash is just sum of chars of string. f1 = t[0] + t[1] + t[2].. + t[len - 1]
Second hash is sum of chars multiplied with coefficients. f2 = 1 * t[0] + 2 * t[1] + 3 * t[2].. + len * t[len - 1]

I search string T in string S using strcmp. I make actual comparision of string T and substring of S only when values of hash functions are equal.

[Helaluddin_brur]

removed after accepted

[brianfry713]

Helaluddin_brur, Read the post before yours

[gautamzero]

why TLE??

Code: Select all

#include <cstdio>
#include <string>
#include <iostream>
using namespace std;

int main()
{
    int t,q;
    string a;
    string b;
    scanf("%d",&t);
    while(t--)
    {
        cin>>a;
        scanf("%d",&q);
        while(q--)
        {
            cin>>b;
            if(a.find(b)!=-1)
                printf("y\n");
            else
                printf("n\n");
        }
    }
    return 0;
}

[brianfry713]

Read this thread, string::find is too slow.

[shahidul_brur]

Why this solution is getting Accepted ?

Code: Select all

#include <stdio.h>
#include<string.h>
int main()
{
    int t,q,i,j,k,len,Y,m,L;
    char ms[100099], ss[1099],p[1099];
    scanf("%d",&t);
    while(t--)
    {
        scanf("%s",&ms);
        scanf("%d",&q);
        len=strlen(ms);
        while(q--)
        {
            scanf("%s",&ss);
            L=strlen(ss);
            for(i=0;i<L;i++)
                p[i]=ms[i];
            p[i]='\0';
            if(strcmp(ss,p)==0)
                printf("y\n");
            else
                printf("n\n");
        }
    }
    return 0;
}

And this solution is not giving the correct output given at uDebug.
This solution will only check whether the given sub-string is a prefix of the main string or not.
But this code is ACCEPTED by UVa oj !! Why ???

So, input contains only the prefix as sub-string ?? Surprising !!