## 10679 - I Love Strings!!

Moderator: Board moderators

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

### 10679 - I Love String!! - Is rejudging possible?

Last year (when I was very new to UVa), I accidentally figure out the test cases of this problem and thus able to generate correct output even without reading the input. I really did so to see how high I can climb on the ranklist.

I now think what I did is a bit childish and like to remove the record. So, is it possible to append one more data set (random data is good enough) to the test cases and rejudge the solutions?

By the way, I believe those sub-1-second solution was doing similar thing as mine to achieve that result. (Please let me know if I am wrong.)

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Hi Cho,

Are you sure you are talking about this problem? I see you have a fast time, but a printf solution would have 0.000 seconds. And yes, my solution is <1 second and it is genuine, as are many other sub second solutions from respectable people.

Personally, I wouldn't bother too much if you've made the occasional misstep; there are enough people who do this systematically without remorse.

For this problem, I don't think it would be a good idea to add more cases: there are some people who just made the time limit, and they would be disadvantaged. You could ask the judges to reorder the testcases, but I don't think they would be very willing to do so.
But I see you have a time of 0.383 seconds. It is a bit of work, but why don't you try to write an even faster genuine solution? It should be possible and then you clean your sleeves.

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong
I didn't keep the cheated solution so don't know exactly what I did. As I can remember, I scanf all the input, then printf the output y or n directly (I can determine the answer with a single if condition only) without any processing of the input strings. And this gave me .383 second.

That's why I think anyone with submission in similar running time cheated as well. I'm sorry about my judgement to those who really solved this problem with decent time.

I know suffix tree or suffix array are the state-of-the-art pattern matching algorithm with linear running time. But there is quite a lot of processing, I really cannot foresee I can implement any of them and solve this problem in less than one second.

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong
I've just submitted the following WA code and it took 0.428 to finish. That's why it's too hard for me to imagine there are genuine solutions to solve it at similar or even faster speed.

Code: Select all

``````#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char text[102400], query[1024];

void main()
{
int t, n;

for(scanf("%d", &t); t--; )
{
scanf("%s", text);

for(scanf("%d", &n); n--; )
{
scanf("%s", query);
printf("%c\n", 'y');
}
}
}``````

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
You can improve much on your reading part. The following gives WA in 0.086 seconds:

Code: Select all

``````#include <stdio.h>

char string[128*1024];
char query[1024];

int main(){
int cases;
int queries;

scanf("%d\n",&cases);
while(cases--){
fgets(string,sizeof(string),stdin);
/* ... */
scanf("%d\n",&queries);
while(queries--){
fgets(query,sizeof(query),stdin);
/* ... */
}
}
return 0;
}
``````
I admit that this code is not very fail-safe, but it worked for me on this problem.
The reason that scanf is so slow for big input is that most compilers don't actually compile code for it, but include a little interpreter that processes the format string and input at runtime.

But it will be a great task to get the rest of the code under 0.3 seconds

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong
joey, thanks a lot for demystifying the ultra fast running time.
Stupid me.. forgetting the fgets function...
Although not as fast, I now manage to finish in 1.5 sec with suffix tree.

Salman
New poster
Posts: 25
Joined: Thu Jun 26, 2003 9:45 am

### Run Time Error

I am having runtime error using strstr function . Can any one tell me Why?

Psyco
New poster
Posts: 14
Joined: Sat Jan 21, 2006 12:39 pm
Contact:

### 10679 - I Love String (STL) Why TLE?

#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
using namespace std;
int n, j, find, i, k;
int main()
{
scanf("%d",&n);
for(j=0;j<n;j++)
{
string s;
cin >> s;
string::size_type idx;
cin >> find;
for(i=0;i<find;i++)
{
k=0; string strFind;
cin >> strFind;

idx=s.find(strFind);
if(idx!=string::npos)
{
string subs = s.substr(idx, strFind.size());
cout << "y" << endl; k=1;
}
idx=s.find(strFind, idx + strFind.size());
if(idx!=string::npos)
{
string subs = s.substr(idx, strFind.size());
cout << "y" << endl; k=1;
}
if(k==0)
cout << "n" << endl;
}
}
return 0;
}

Why TLE?
I used STL.....
Last edited by Psyco on Fri Feb 03, 2006 1:47 pm, edited 1 time in total.

scidong
New poster
Posts: 45
Joined: Sat Jan 21, 2006 12:55 pm
Location: the four-dimensional world

### Oh.

You should search more.
There are many question like your question, and many answers on those
All living things are amazing thing.

Psyco
New poster
Posts: 14
Joined: Sat Jan 21, 2006 12:39 pm
Contact:

### Thanks

Thanks......

But I can't using KMP...

I am serching many question, But they are all says "Using KMP"

Need I using KMP?

타임 리미트...I want to Accpted

scidong
New poster
Posts: 45
Joined: Sat Jan 21, 2006 12:55 pm
Location: the four-dimensional world

### Then...

All living things are amazing thing.

tmdrbs6584
Learning poster
Posts: 98
Joined: Sat Jan 21, 2006 12:45 pm
Location: Busan,Corea(Republic of)

### RE:&#47932;&#51020;

You are Hooked up!!!

Psyco
New poster
Posts: 14
Joined: Sat Jan 21, 2006 12:39 pm
Contact:

### 10679 - I Love String ( STL ) Why TLE???

#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
using namespace std;
int n, j, find, i, k;
int main()
{
scanf("%d",&n);
for(j=0;j<n;j++)
{
string s;
cin >> s;
string::size_type idx;
cin >> find;
for(i=0;i<find;i++)
{
k=0; string strFind;
cin >> strFind;

idx=s.find(strFind);
if(idx!=string::npos)
{
string subs = s.substr(idx, strFind.size());
cout << "y" << endl; k=1;
}
idx=s.find(strFind, idx + strFind.size());
if(idx!=string::npos)
{
string subs = s.substr(idx, strFind.size());
cout << "y" << endl; k=1;
}
if(k==0)
cout << "n" << endl;
}
}
return 0;
}

Why TLE?
I used STL.....

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Psyco wrote:Why TLE?
I used STL.....
AFAIK, STL string's find() is implemented with O(nm) algorithm (n,m=length of strings.)
It would be a too trivial problem, if such algorithms were allowed to pass!
Need I using KMP?
You can also use suffix trees/arrays or Aho-Corasick to get accepted.