Fastest way to read strings

1

In many problems, I have seen that we need to input a string where it is not preceded by its length. In such cases the almost only way seems to be to use std::cin to read the string, which, even with ios_base::sync_with_stdio(false) and cin.tie(NULL) seems very slow. However without the length I dont know how to read it using scanf or fgets.
Further, I’ve learnt c++ properly but not c, though I’ve coded a bit in c before, so I don’t know a great deal about the routines used in c.
What’s the best way to read the string in such cases?

2

Read this–> Here

2 Likes
3

What makes you say that?

>cat 10-big-strings.txt | time -p ./a.out 
Read string of size: 999993
Read string of size: 999991
Read string of size: 999997
Read string of size: 999998
Read string of size: 999997
Read string of size: 999999
Read string of size: 999993
Read string of size: 999996
Read string of size: 999995
Read string of size: 999999
real 0.03
user 0.01
sys 0.01
2 Likes
4

I read it off a blog post on codeforces which compared the time taken by scanf with the time taken by the optimized istream functions for a wide class of data types.
I was led to making this post because my \mathcal O (N \log N) suffix array solution to “ADAPHOTO” on spoj gave TLE, and I have optimizied literally everything I could except the cin >> (string stuff) part. I’m now trying to use the suffix tree to build the suffix array in \mathcal O(N) but somehow it takes > 3 seconds for N \sim 2 \cdot 10^5 :face_with_raised_eyebrow: . I’ll have to debug uff.

1 Like
5

Oh, OK - looks like ADAPHOTO has two strings of size up to 10^6, so reading in the strings should be almost instantaneous, but an O(N log N) suffix array construction probably won’t be fast enough.

Which is why I always use Ukkonen’s Algorithm for these kind of things :slight_smile:

2 Likes
6

Yeah, I’m now using ukkonen to make a suffix tree then using dfs to make the suffix array. Its taking > 3 seconds on random testcases with string sizes 200000 though…
Maybe I’ll look for a way to solve it directly from the suffix tree. Uff…
Thanks for the info.:slightly_smiling_face:

1 Like
7

I think every string problem I’ve solved, I’ve solved it directly using the Suffix Tree/ Suffix Automaton.

1 Like
8

In C you usually allocate the size of char array according to constraints, For example, char[1000000].
And then you can scan through scanf. For the actual size use strlen() or traverse till the ‘\0’.

1 Like