10679 - I Love Strings!!

All about problems in Volume 106. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

shikhorroy
New poster
Posts: 27
Joined: Sat Jul 27, 2013 3:52 am

Submission Error: 10679 - I Love Strings!!

Post by shikhorroy » Sat Jul 27, 2013 4:17 am

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: Submission Error: 10679 - I Love Strings!!

Post by brianfry713 » Mon Jul 29, 2013 4:38 am

See on uva.onlinejudge.org "Information on Submission Errors"
Check input and AC output for thousands of problems on uDebug!

shikhorroy
New poster
Posts: 27
Joined: Sat Jul 27, 2013 3:52 am

Re: Submission Error: 10679 - I Love Strings!!

Post by shikhorroy » Fri Aug 02, 2013 5:42 pm

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

sobhan_cp
New poster
Posts: 1
Joined: Wed Jul 24, 2013 12:12 am

Re: Submission Error: 10679 - I Love Strings!!

Post by sobhan_cp » Sun Sep 08, 2013 6:20 pm

i got submission error too
what is the se ??

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: Submission Error: 10679 - I Love Strings!!

Post by brianfry713 » Mon Sep 09, 2013 9:56 pm

Check input and AC output for thousands of problems on uDebug!

ehsanulbigboss
New poster
Posts: 32
Joined: Tue Jul 22, 2014 1:17 am

Re: 10679 - I Love Strings!!

Post by ehsanulbigboss » Fri Oct 24, 2014 10:57 am

:oops: :oops: :oops: :oops:
Last edited by ehsanulbigboss on Thu Feb 05, 2015 10:00 pm, edited 1 time in total.

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 10679 - I Love Strings!!

Post by lighted » Fri Oct 24, 2014 4:24 pm

If you read this thread you would see that this problem can be solved by Aho-Corasick or suffix tree or hash function...
Observer wrote:
Adrian Kuegel wrote: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.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

Helaluddin_brur
New poster
Posts: 15
Joined: Tue Oct 21, 2014 4:08 pm
Location: Bangladesh
Contact:

Re: 10679 - I Love Strings!!

Post by Helaluddin_brur » Sat Dec 13, 2014 12:44 pm

removed after accepted :D :D :D
Last edited by Helaluddin_brur on Tue Jan 03, 2017 7:50 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10679 - I Love Strings!!

Post by brianfry713 » Sat Dec 13, 2014 8:40 pm

Helaluddin_brur, Read the post before yours
Check input and AC output for thousands of problems on uDebug!

gautamzero
New poster
Posts: 32
Joined: Fri Oct 10, 2014 1:10 pm
Location: Sylhet, Bangladesh

Re: 10679 - I Love Strings!!

Post by gautamzero » Tue Dec 16, 2014 10:24 am

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;
}
None but a fool is always right..
so don't be upset when u r wrong..

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10679 - I Love Strings!!

Post by brianfry713 » Tue Dec 16, 2014 9:40 pm

Read this thread, string::find is too slow.
Check input and AC output for thousands of problems on uDebug!

shahidul_brur
New poster
Posts: 12
Joined: Sun Sep 20, 2015 12:33 pm

Re: 10679 - I Love Strings!!

Post by shahidul_brur » Fri Dec 02, 2016 8:17 pm

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 !!

Post Reply

Return to “Volume 106 (10600-10699)”