[P5] 백준 1786번 찾기 C++ KMP, 문자열, LPS

리뷰

 

KMP의 기초가 되는 문제, O(M+N)의 시간 복잡도로 해당 문제를 푸는게 놀라울 따름이다.

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

 

전역 변수

• str1, str2 : 원본 문자열 str1, 원본 문자열에서 패턴을 찾을 문자열 str2
• n, m, cnt : str1의 길이 n, str2의 길이 m, str1에서 str2를 찾은 개수 cnt
• lps, ans : 부분 문자열의 lps를 구할 정수형 벡터 lps, 찾은 인덱스를 저장할 정수형 벡터 ans

 

함수

1. getLPS

void getLPS(const string& str2)

 

패턴 문자열 str2에서 LPS를 구하기 위한 함수

1. lps벡터를 m크기로 초기화 해준다. lps[0]은 0으로 초기화 해야하므로 일단 모두 0으로 초기화 해주었다.
2. cur = 0, i = 1부터 시작하여 i가 str2의 길이 m보다 작을경우 while루프를 실행해 준다.
3. 만약 str2[cur]과 str2[i]가 같을 경우 lps[i]를 cur + 1로 저장해 주고 cur과 i를 모두 증가시킨다.
4. 아닐 경우 cur이 0보다 크다면 cur을 lps[cur - 1]로 변경해 준다.
5. cur이 0일 경우엔 lps[i]를 0으로 설정하고 i를 증가시켜 준다.

 

2. KMP

void KMP(const string& str1, const string& str2)

 

KMP를 통해 원본 문자열에서 패턴 문자열을 찾아주는 함수

1. i, j를 각각 str1, str2의 탐색 인덱스로 사용해 준다.
2. i가 원본 문자열의 길이 n보다 작을 경우 while을 통해 루프를 돌아준다.
3. 만약 str1[i]과 str2[j]가 같을 경우 i와 j를 모두 증가시켜 준다.
4. 만약 j와 m이 동일할 경우 원본 문자열에서 패턴을 찾은 케이스이다.
5. cnt를 증가시켜 주고 ans에 i - j + 1을 추가해 준다, 1-based-indexing이므로 1을 증가시켜 준 것이다.
6. 이후 j를 lps[j - 1]로 변경해 준 뒤에 탐색을 계속 진행한다.
7. 만약 j와 m이 다를 경우 i가 n보다 작고, str2[j]와 str1[i]가 다르고 j가 0이 아니라면 j를 lps[j - 1]로 변경해 준다.
8. j가 0이라면 i를 증가 시킨 후에 탐색을 진행해 준다.

 

문제풀이

1. 문자열에 띄워쓰기가 포함되어 있으므로 getline을 통해 str1과 str2를 입력 받아준다.
2. n과 m에 각각 str1의 길이와 str2의 길이를 저장해 준다.
3. getLPS 함수를 통해 str2의 LPS를 구해준 후 lps벡터에 그 값을 저장해 준다.
4. KMP 함수를 통해 str1에서 str2가 몇번 찾을 수 있는지 개수와 인덱스 정보를 저장해 준다.
5. 탐색을 마친 후 cnt를 출력해 주고 줄바꿈한 뒤에 공백을 기준으로 각각의 인덱스를 출력해 준다.

 

참고 사항

• KMP에서 i와 j가 증가된 상태에서 i가 n값을 넘어갈 수 있기 때문에 i < n를 조건문에 추가해 주어야 한다.
• str1과 str2모두 띄워쓰기가 포함될 수 있다, 두 문자열 모두 getline으로 입력 받아주어야 한다.

 

정답 코드

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

using namespace std;
string str1, str2;
int n, m, cnt;
vector<int> lps, ans;

void getLPS(const string& str2) {
	int cur = 0, i = 1;
	lps.resize(m, 0);
	while (i < m) {
		if (str2[cur] == str2[i]) {
			cur++;
			lps[i] = cur;
			i++;
		}
		else {
			if (cur != 0) cur = lps[cur - 1];
			else {
				lps[i] = 0;
				i++;
			}
		}
	}
}

void KMP(const string& str1, const string& str2) {
	int i = 0, j = 0;
	while (i < n) {
		if (str1[i] == str2[j]) {
			i++;
			j++;
		}

		if (j == m) {
			cnt++;
			ans.push_back(i - j + 1);
			j = lps[j - 1];
		}
		else if (i < n && str2[j] != str1[i]) {
			if (j != 0) j = lps[j - 1];
			else i++;
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	getline(cin, str1);
	getline(cin, str2);

	n = str1.size(), m = str2.size();
	getLPS(str2);
	KMP(str1, str2);

	cout << cnt << "\n";
	for (const int& a : ans) cout << a << " ";
}