 < 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, 6:34 p.m. Last updated on April 7, 2019, 6:34 p.m.

Preview

##### Enter your comment details below:

Preview

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, 6:34 p.m.

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