BOJ

BOJ::1786 찾기

BOJ Gold 1

BOJ::1786 찾기

Link : BOJ::1786
bowbowbow : KMP
Level : Gold 1
tag : KMP, string

시사점

KMP 알고리즘을 학습할 수 있는 좋은 문제입니다.
KMP에 대한 학습은 링크 걸어둔 bowbowbow님의 블로그를 참고하였습니다.
- 문자열 검색 알고리즘으로, string s에서 string p가 총 몇번나오는지 빠르게 계산하는 알고리즘입니다.
- s의 길이를 n, p의 길이를 m이라고 할때 O(n+m)의 복잡도를 가집니다.
- naive하게 brute force로 문제를 해결하려면 O(NM)이 나오게 되죠.
- 방법은 간단하게 다음과 같습니다.
  - string p를 훑어보며 배열 pi를 만듧니다.
    - pi[i] : 구간 [0:i]까지의 부분 문자열 중에서 prefix == suffix가 될 수 있는 부분 문자열 중 가장 긴것의 길이
  - 이제 pi를 들고, s와 p를 비교하며 pattern이 등장하는 갯수를 카운트 합니다.

이해(x)

string s와 string p가 주어집니다.
s에 p가 몇번 등장하는지, 어느 인덱스에 등장하는지 출력합니다.

설계, 손 코딩(x)

손으로 중심이 되는 코드를 구현합니다.
시사점 챕터에 기술한 KMP알고리즘을 이용하여 구현합니다.

복잡도

O(N + M)

구현(x)

#include<iostream>
#include<string>
#include<vector>
#define rep(i, a, b) for(int i=(a);i<(b); i++)
#define r_rep(i,a,b) for(int i=(a);i>(b); i--)
const int MAX = 1000000 + 100;
typedef long long ll;
using namespace std;

string A, B;
int pi[MAX];
void getPi() {
	int len = B.size();
	int j = 0;
	rep(i, 1, len) {
		while (j > 0 && B[i] != B[j])
			j = pi[j - 1];
		if (B[i] == B[j])
			pi[i] = ++j;
	}
}
void kmp() {
	int len1 = A.size(), len2 = B.size();
	int j = 0;
    vector<int> ans;
	rep(i, 0, len1) {
		while (j > 0 && A[i] != B[j])
			j = pi[j - 1];
		if (A[i] == B[j]) {
			if (j == len2 - 1) {
				ans.push_back(i-len2+1);
				j = pi[j];
			}
			else
				j++;
		}
	}
    cout <<  ans.size() << '\n';
    rep(i, 0, ans.size()) cout << ans[i] + 1<< '\n';
}
void FindString() {
	rep(i, 0, MAX) pi[i] = 0;

	getPi();
	kmp();
}
int main(){
	getline(cin, A);
	getline(cin, B);
    FindString();
    return 0;
}