<백준 알고리즘> KMP 알고리즘 1786번

KMP 알고리즘

문자열을 탐색할 때 사용하는 알고리즘이다.

핵심 아이디어는 찾고자 하는 문자열의 접두사(prefix)와 접미사(suffix)에 대하여 일치하는 개수(길이)를 배열로 저장한 후에 탐색할 때 사용하는 것이다.

예를 들어 찾고자 하는 문자열 p가 ababc 일 경우
i = 0, 0
i = 1, 0
i = 2, aba 에서 a, a이므로 1
i = 3, abab에서 ab와 ab이므로 2
i = 4, 접미사가 c로 시작하므로 일치하는 것이 없다 0

이렇게 배열을 만든 후 찾고자하는 문자열 s가 ababdababcababc일 경우

j = 0(p에서 쓰이는 인덱스), i = 0 (s에서 쓰이는 인덱스)

처음에 ababd에 대하여 abab까지 같으므로 j = 4 , i = 4이고 다음 상황에 c != d이므로 j를 옮겨 줘야 한다 이때 미리 구해둔 pi배열을 쓰는데 위에서 보든 pi[3]일때 즉 abab였을 때 접두사 == 접미사 중 가장 긴 것의 길이가 2인 ab를 저장해두었으므로 j = 2인데 [2]또한 다르기 때문에 한 번더 옮겨주면 j = 0으로 다시 시작하게 된다.

쉽게 얘기해서 굳이 처음부터 다시 비교하는 것이 아닌 미리 저장해둔 위치로 이동해서 더 효율적으로 탐색하는 것이다.

이후 계속 보면 ababc가 겹치므로 정답을 추가하고 j = 0이 되어 다시 진행 하면 ababc가 또 나오므로 총 2개의 문자열이 탐색된다.

백준 1786번 문제

백준 1786번

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <functional>


using namespace std;

int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };




vector<int> getPi(string p)
{
	int m = p.size();
	int j = 0;

	vector<int> pi(m, 0);

	for (int i = 1; i < m; i++)
	{
		while (j > 0 && p[i] != p[j])
			j = pi[j - 1];

		if (p[i] == p[j])
			pi[i] = ++j;
	}

	return pi;
}

vector<int> kmp(string s, string p)
{
	vector<int>ans;

	auto pi = getPi(p);
	
	int n = s.size(); int m = p.size(); int j = 0;

	for (int i = 0; i < n; i++)
	{
		while (j > 0 && s[i] != p[j])
			j = pi[j - 1];

		if (s[i] == p[j])
		{
			if (j == m - 1)
			{
				ans.push_back(i - m + 1);
				j = pi[j];
			}
			else
			{
				j++;
			}
		}
	}

	return ans;
}


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

	string T, P;

	getline(cin, T);

	getline(cin, P);


	vector<int> a = kmp(T, P);

	cout << a.size() << "\n";

	for (int i = 0; i < a.size(); i++)
	{
		cout << a[i] + 1 << " ";
	}

	return 0;
}