Page 7 of 7
Submission Error: 10679 - I Love Strings!!
Posted: Sat Jul 27, 2013 4:17 am
by 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;
}
Re: Submission Error: 10679 - I Love Strings!!
Posted: Mon Jul 29, 2013 4:38 am
by brianfry713
See on uva.onlinejudge.org "Information on Submission Errors"
Re: Submission Error: 10679 - I Love Strings!!
Posted: Fri Aug 02, 2013 5:42 pm
by shikhorroy
Hmm...mmm...
but I think this is a server problem.
Re: Submission Error: 10679 - I Love Strings!!
Posted: Sun Sep 08, 2013 6:20 pm
by sobhan_cp
i got submission error too
what is the se ??
Re: Submission Error: 10679 - I Love Strings!!
Posted: Mon Sep 09, 2013 9:56 pm
by brianfry713
Re: 10679 - I Love Strings!!
Posted: Fri Oct 24, 2014 10:57 am
by ehsanulbigboss
Re: 10679 - I Love Strings!!
Posted: Fri Oct 24, 2014 4:24 pm
by lighted
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.
Re: 10679 - I Love Strings!!
Posted: Sat Dec 13, 2014 12:44 pm
by Helaluddin_brur
Re: 10679 - I Love Strings!!
Posted: Sat Dec 13, 2014 8:40 pm
by brianfry713
Helaluddin_brur, Read the post before yours
Re: 10679 - I Love Strings!!
Posted: Tue Dec 16, 2014 10:24 am
by 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;
}
Re: 10679 - I Love Strings!!
Posted: Tue Dec 16, 2014 9:40 pm
by brianfry713
Read this thread, string::find is too slow.
Re: 10679 - I Love Strings!!
Posted: Fri Dec 02, 2016 8:17 pm
by 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 !!