< Back to forum

in this question i am not able to solve some of the test cases :when there is more than one occurence of same string is happening like test case 9 ,link -> https://www.hackerrank.com/challenges/the-grid-search/problem

#include<bits/stdc++.h>
#include<string.h>
#include<iostream>

using namespace std;

int main()
{

int t;
cin>>t;
int r,c,i,j,rq,cq;

while(t--)
{
    int f=0,k=0;
    cin>>r>>c;
    vector<string> s;
    vector<string> sq;

    string z;

    for(i=0;i<r;i++)
    {
        cin>>z;
        s.push_back(z);
    }



    cin>>rq>>cq;

    for(i=0;i<rq;i++)
    {
        cin>>z;
        sq.push_back(z);
    }

vector<size_t> ansr;
vector<size_t> ansc;


 j=0;
 std::size_t found =0;
int ar=0,t=0;

    for(i=0;i<rq;i++)
    {

     j=t;
     // 
      for(;j<r;j++)
       {

         ar++;
         found =s[j].find(sq[i]);
          
         //cout<<sq[i]<<"\n";
            if (found!=std::string::npos)
                {
                    //cout<<found<<" found ";
                     // cout<<ar<<" row ";
                      ansr.push_back(ar);
                      ansc.push_back(found);
                       t=j+1;
                   //   cout<<ansr[f]<<" ans ";
                      f++;
                      break;
                }
                
                else if(f>0)
                {
                  ar=ar+2;
                  ansr.push_back(ar);
                  f++;
                  break;
                }

       }

    }


   // for(i=0;i<f;i++)
       //   cout<<ansr[i]<<" "<<ansc[i]<<"\n";

int row=0;

   for(i=0;i<f-1;i++)
    {
      row=ansr[i+1]-ansr[i];  
     // cout<<ansc[i]<<" "<<ansr[i]<<"\n";
      
     if((ansc[i]!=ansc[i+1])||(row!=1))
     {
         k=1;
         break;

     }

    }


    if(k==1)
        cout<<"NO";

    else
        cout<<"YES";


cout<<endl;


}


    return 0;
}

 

Asked by: Manish_Kumar_Savita on April 7, 2019, 1:04 p.m. Last updated on April 7, 2019, 1:04 p.m.


Enter your answer details below:


Preview

Enter your comment details below:

Preview




1 Answer(s)

avatar

Firstly, don't use string::find. You should try to match the pattern (r x c) with all the sub-grids of size (r x c) in the grid of size (R x C) manually character by character, break as soon as a character is a mismatch and start with another sub-grid. But the time complexity of that will be O((R-r)*(C-c)*(r*c)), the worst case is when r=R/2 and c=C/2. Though I think this should pass as tests may not be that strong. 

We can improve on this by maintaining a 2-D prefix sum of the grid and matching only those sub-grids whose sum matches with the sum of the pattern. 

Saptarshi_Dey last updated on April 7, 2019, 1:04 p.m. 0    Reply    Upvote   

Instruction to write good question
  1. 1. Write a title that summarizes the specific problem
  2. 2. Pretend you're talking to a busy colleague
  3. 3. Spelling, grammar and punctuation are important!

Bad: C# Math Confusion
Good: Why does using float instead of int give me different results when all of my inputs are integers?
Bad: [php] session doubt
Good: How can I redirect users to different pages based on session data in PHP?
Bad: android if else problems
Good: Why does str == "value" evaluate to false when str is set to "value"?

Refer to Stack Overflow guide on asking a good question.