[hacker rank] The grid search

문제 링크

 

풀이

그리드 배열에서 패턴 배열의 첫 번째 요소과 일치하는 문자열의 위치를 찾을 때마다 나머지 패턴을 비교했습니다. 패턴 배열의 첫 번째 요소와 일치하는 그리드 배열의 행의 위치가 패턴 배열의 크기보다 작으면 탐색을 멈춥니다. 탐색을 멈출 때까지 return이 이뤄지지 않았다면 그리드 배열에서 패턴을 찾지 못한 것입니다.

 

코드

string gridSearch(vector<string> G, vector<string> P)
{
	for (size_t i = 0; i < G.size(); ++i)
	{
		if (i > G.size() - P.size())
			break;
		size_t col = 0;
		while (true)
		{
			col = G[i].find(P[0], col);
			if (string::npos == col)
				break;
			else
			{
				size_t index = i + 1;
				bool flag = true;
				for (size_t j = 1; j < P.size(); ++j)
				{
					string temp = G[index++].substr(col, P[j].size());
					if (temp != P[j])
					{
						flag = false;
						break;
					}
				}
				if (true == flag)
					return "YES";
			}
			++col;
		}
	}
	return "NO";
}