Optimize an algorithm to find multiple specific substrings of a string

user_9702817 0
Viewed 254

I'm new to C++ coding and just started solving competitive programming problems. I want to solve the following task: https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1620.
I want to find a substring of a string. The problem is that the code below is slow and I fail the submission by getting the "time limit exceeded" "error". What can I do to speed up the code?

#include <iostream>
#include <sstream>
#include <stdio.h>
#include <string.h>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    stringstream ss;
    string m;
    char prob[100000];
    char substring[1000];
    int howManyCases = 0;
    int numberOfTests = 0; 

    cin >> numberOfTests;
    cin.ignore();
    while(numberOfTests--)
    {
        cin >> prob >> howManyCases;

        while(howManyCases--)
        {
            cin >> substring;
            if (strstr(prob,substring)) {
                ss << 'y' << "\n";
            }
            else
            {
                ss << 'n' << "\n";
            }
        }
    }

    m = ss.str();
    cout << m;

    return 0;
}
substring optimization c++
1 Answers

i would make you of <algorithm> header:

std::string parent_string = "some string lala";
std::string sub_string = "lala";
auto found = parent_string.find(sub_string);

it will return iterator to where substring is. Then I wou;d use this clause:

if (found != std::string::npos) std::cout << "y\n";
else std::cout << "n\n";

If there is no limitation to the use of standard libraries, It's always a better choice to use it instead of creating your own algorithms (that may not handle some special cases you won't think of ). Also, swap those huge ugly c-style arrays to std::string.

user_166247550
Related