백준 - 찾기(1786)

 

과거 kmp알고리즘을 공부한 적이 있는데 이를 이용하는 문제이다.

문자열을 비교할 때 건너뛰면서 비교하는 기법이다.

 

 

 

#include <iostream>
#include <vector>
#include <string>

using namespace std;

vector<int>	make_pi(string pattern)
{
	vector<int> pi(pattern.size(), 0);
	int i = 0;
	for (int j = 1; j < pattern.size(); j++) {
		while (i > 0 and pattern[i] != pattern[j]) i = pi[i - 1];
		if (pattern[i] == pattern[j]) {
			i++;
			pi[j] = i;
		}
	}

	return pi;
}

int main()
{
	string text;
	string pattern;
	
	getline(cin, text);
	getline(cin, pattern);

	vector<int> pi = make_pi(pattern);
	vector<int> answer;
	int i = 0;
	for (int j = 0; j < text.size(); j++) {
		while (i > 0 and pattern[i] != text[j]) i = pi[i - 1];
		if (pattern[i] == text[j]) {
			i++;
			
			if (i > pattern.size() - 1)
			{
				answer.push_back(j - i + 2);
				i = pi[i - 1];
			}
		}
	}

	cout << answer.size() << endl;
	for (int i = 0; i < answer.size(); i++) cout << answer[i] << " ";
}

먼저 패턴을 이용해 파이 테이블을 만들어준다.

파이 테이블은 접두사와 접미사가 같은 최대 문자열을 기록해 둔다.

 

A B A  A B A B

 

A X A X X X X

0 0 1 0 0 0 0

 

A X X A X X X

0 0 1 1 0 0 0

 

A B X A B X X

0 0 1 1 2 0 0

 

A B A A B A X

0 0 1 1 2 3 0

 

이와 같은 방식으로 만들어진다.

이 테이블을 이용해서 반복되는 구간을 이용해 비교해 가며 패턴을 찾는다.

코드의 i = pi [i-1]이

비교할 패턴을 뛰어넘으면서 비교하게 해 준다.