백준 - 1543번 문서 검색 (C++)

https://www.acmicpc.net/problem/1543

1543번: 문서 검색

 이번 문제는 문서라는 이름의 문자열과 단어라는 이름의 문자열이 주어진다. 그리고 이 문서에 단어가 중복되지 않게 최대 몇 개가 등장하는지를 구하는 문제이다. 처음 이 문제를 보았을 때, KMP 알고리즘 생각이 살짝 나서 두려웠다. 왜냐하면 문자열 알고리즘은 도저히 적응이 되지 않았기 때문이다. 하지만 문제 조건을 다시 한 번 보니 저런 알고리즘을 이용하지 않아도 될 것 같다는 생각이 들었다. 왜냐하면 문서의 길이는 최대 2500자이고 단어 길이는 최대 50자이기에, 최악의 경우라도 그렇게 시간이 많이 걸릴 것 같지 않았기 때문이다. 그래서 그냥 무작정 모든 경우를 다 검사하게 코드를 작성하였다.

 

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <memory.h>
#include <deque>
#include <cmath>
#include <stack>
#include <cstring>
#include <typeinfo>
#include <iomanip>
#include <limits.h> 
#include <map>
#pragma warning(disable:4996)

using namespace std;

string sentence;
string pattern;

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

	int count = 0;

	getline(cin, sentence);
	getline(cin, pattern);

	int lastIdx = sentence.size() - pattern.size();

	for (int startIdx = 0; startIdx <= lastIdx; ++startIdx)
	{
		bool isSame = true;

		for (int sentIdx = startIdx, idx = 0; idx < pattern.size(); ++idx, ++sentIdx)
		{
			if (pattern[idx] != sentence[sentIdx])
			{
				isSame = false;
				// startIdx = sentIdx;
				break;
			}
		}

		if (isSame)
		{
			++count;
			startIdx += (pattern.size() - 1);
		}
	}

	cout << count << endl;

    return 0;
}