단순 구현

// '짚더미' H의 부분 문자열로 '바늘' N이 출현하는 시작 위치들을 모두 반환한다.
vector<int> naiveSearch(const string& H, const string& N)
{
	vector<int> ret;
	// 모든 시작 위치를 다 시도해 본다.
	for (int begin = 0; begin + N.size() <= H.size(); ++begin)
	{
		bool matched = true;
		for (int i = 0; i < N.size(); ++i)
		{
			if (H[begin +i] != N[i])
			{
				matched = false;
				break;
			}
			if (matched) ret.push_back(begin);
		}
	}
	return ret;
}

최악의 경우는 N이 H의 모든 Index에서 출현하는 경우이다. 이거는 O(|N| * |H|) 의 시간 복잡도. 그러나 구현이 단순해서 C++ string::find()는 이를 사용.