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?

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
```

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 . I’ll have to debug uff.

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

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.

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

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