Page 1 of 1

Why STL is TLE? I don't want to KMP........Plzzzzzzzzzzz

Posted: Fri Feb 03, 2006 1:48 pm
by Psyco
#include <iostream>
#include <string>
#include <cstdio>
#include <cstring>
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,strFind.size());
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 am using STL.................WhY?

Posted: Wed Apr 05, 2006 11:10 pm
by Moha
I am not sure, but it is not a good idea to use cin and scanf both in a source code. anyway, string is very slow(because vector is very slow) but in uva you can find some problem, in which if you write them by stl, you will get TLE, and you should write your own methods. one of the example of these problems is 127. if you write it with stl stack you will get TLE.

One simple reason, each access to a one element of a string, it costs 2 function calls.