sam thornton sam thornton - 11 months ago 37
C++ Question

C++ - string Input in a specific way

I want to take input from user in a specific way like in the following manner :

L1 L2 L3 N

L1,L2,L3 are strings separated by whitespace. And N is a integer. I tried using
but it was slow. I need to get the input fast. Also the string L2 in repeated N times. So I have to store
l1 + l2*N + l3
. I tried string but it's becoming too slow. I'm getting TLE.

Here's how I stored them :

using namespace std;
int main (){
string l1,l2,l3;
int n;
string r;
r.reserve(l1.size()+n * l2.size()+l3.size());
r += l1;
for (int i=0; i<n;i++)
r +=l2;

r += l3;
return 0;

And then iterated it in 2 separate for loops with maximum 1000 iterations in each loop.

How can I efficiently store them ? I know about vectors but I'm not good at them. So if anyone knows how to store them in this sequence in vector please help me out. Or if they could be stored on character array, then how to do that way ?

Answer Source

Okay. So let's start by isolating the actual reading from the other code:

struct foo { 
    std::string l1, l2, l3; 
    int n;

    friend std::istream &operator>>(std::istream &is, foo &f) { 
       return is >> f.l1, >> f.l2 >> f.l3 >> n;

With that we can read in a file full of these records into a vector with something like this:

std::vector<foo> data { std::istream_iterator<foo>(infile), {} };

I'd guess that (by itself) won't be a bottleneck. There are probably faster ways to do the job if truly necessary, but I doubt it's really needed.

Based on the comments on how the searching needs to be done, we can do the searching without ever expanding the second string out to n occurrences of l2.

The searching is for one character from the beginning of the string up until the last (right-most) occurrence of some other character.

Since that "end" pattern is a single character, we can do this pretty easily without expanding the middle string (L2) at all. The logic is basically:

if L3 contains end_pattern
   total = count(L1) + count(L2) * n + count(L3.substr(0, pattern_pos))
else if L2 contains end_pattern
    total = count(L1) + count(L2) * (n-1) + count(L2.substr(0, pattern_pos))
else if L1 contains end_pattern
    total = count(L1.substr(0, pattern_pos))
    total = 0; // pattern isn't present anywhere

At least as described in the comments, there doesn't seem to be any need for the O(N2) algorithm described in the comments.