[백준 1786번] - 찾기(C/C++)

1786번: 찾기

[문제 설명]

---

[문제 풀이]

해당 문제는 KMP알고리즘을 이용하여 문자열 패턴 매칭을 하는 문제이다.

따라서 KMP 알고리즘에 대한 이해가 필요하다. 혹시 해당 알고리즘에 대해 잘 모른다면 아래 포스트를 참고하길 바란다.

[Algorithm] - 문자열 탐색 알고리즘 : KMP

문자열 탐색하는 알고리즘이 여러가지 있지만, 가장 쉽게 구현 할 수 있는것은 naive 문자열 탐색 알고리즘이다.

문자열 전체를 하나하나를 탐색하는 방법으로 쉬운만큼 효율적이지 못하다.

따라서 문제에서 요구하는 내용인 KMP 알고리즘을 사용하면 간단하게 해결 할 수 있다.

KMP알고리즘을 적용하면 간단하지만.. KMP 알고리즘 자체의 난이도는 쉽지않아서 이해하는데 오래걸렸다.

위 포스트의 코드에서 패턴이 매칭되는 횟수를 세어주고, 각각의 인덱스를 vector에 담아서 출력해주면 된다.

 

문제의 입력이 공백이 포함되는 문자열이라 getline(cin, string) 함수를 사용하여 공백이 포함된 문자열을 입력으로 받아주면 된다.

 

[코드]

[GitHub]

GitHub - EGyeom/BlogMaker: this is Blog Maker

코드가 깨끗하고 명확하게 보일진 모르겠지만, 누군가에게 도움이 될 수도.. 있기에..

#include <bits/stdc++.h>
using namespace std;


vector<int> makeTable(string pattern)
{
	int patternSize = pattern.length();
	vector<int> table(patternSize, 0);
	int j = 0;
	for(int i = 1; i < patternSize; i++)
	{
		while(j > 0 && pattern[i] != pattern[j])
			j = table[j-1];

		if(pattern[i] == pattern[j])
		{
			table[i] = ++j;
		}
	}

	return table;
}

void KMP(string s, string pattern)
{
	vector<int> table = makeTable(pattern);
	int sSize = s.length();
	int patternSize = pattern.length();
	int j = 0;
	int count = 0;
	vector<int> indexVector;

	for(int i = 0; i < sSize; i++)
	{
		while(j > 0 && s[i] != pattern[j])
			j = table[j-1];
		
		if(s[i] == pattern[j])
		{
			j++;
			if(j == patternSize)
			{
				count++;
				indexVector.emplace_back(i - j + 2);
				j = table[j-1];
			}
		}
	}

	cout << count << "\n";
	for(int& index : indexVector)
	{
		cout << index << " ";
	}
	cout << "\n";
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	string s, pattern;
	getline(cin, s);
	getline(cin, pattern);

	KMP(s,pattern);
}