10679 - I Love Strings!!

[Cho]

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]

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]

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]

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]

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]

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]

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

[Psyco]

#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.....

[scidong]

You should search more.
There are many question like your question, and many answers on those

[Psyco]

Thanks......

But I can't using KMP...

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

Need I using KMP?

Please.... Hint....

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

[scidong]

Then, Ask your tutor.

[tmdrbs6584]

You are Hooked up!!!

[Psyco]

#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]

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.

P.S. Please, don't create several identical threads!

[scidong]

Ye...
That must be TLE.
plz use kmp!