백준 16916 부분 문자열 c++ (kmp)

문제 출처 : https://www.acmicpc.net/problem/16916

16916번: 부분 문자열

문제

문자열 S의 부분 문자열이란, 문자열의 연속된 일부를 의미한다.

예를 들어, "aek", "joo", "ekj"는 "baekjoon"의 부분 문자열이고, "bak", "p", "oone"는 부분 문자열이 아니다.

문자열 S와 P가 주어졌을 때, P가 S의 부분 문자열인지 아닌지 알아보자.

입력

첫째 줄에 문자열 S, 둘째 줄에 문자열 P가 주어진다. 두 문자열은 빈 문자열이 아니며, 길이는 100만을 넘지 않는다. 또, 알파벳 소문자로만 이루어져 있다.

출력

P가 S의 부분 문자열이면 1, 아니면 0을 출력한다.

알고리즘 분류

• 문자열
• kmp

풀이

완전한 kmp 기본 문제이다.

문제를 풀기 전 kmp 알고리즘을 우선 학습하길 바란다.

최근에 코테에서 kmp의 실패 함수를 응용한 문제가 나온 만큼,

실패함수는 간혹가다 문자열 비교 알고리즘에서 응용해야 하는 경우가 있다!

자주 푸는 알고리즘은 아니지만, 적어도 실패 함수만큼은 까먹지 말자! 실패 함수 짤 수 있으면 나머지 kmp 짜는 것도 어렵지 않다. 

 

코드

#include <iostream>
#include <string>
#include <vector>
using namespace std;


vector<int> makeTable(string p) {
	vector<int> table(p.length());
	int j = 0;
	for (int i = 1; i < p.length(); i++) {
		while (p[i] != p[j] && j > 0) {
			j = table[--j];
		}
		if (p[i] == p[j]) {
			table[i] = ++j;
		}
	}
	return table;
}

int kmp(string s, string p, vector<int> &table) {
	int j = 0;
	for (int i = 0; i < s.length(); i++) {
		while (s[i] != p[j] && j > 0) {
			j = table[--j];
		}
		if (s[i] == p[j]) {
			if (++j == p.length()) {
				return 1;
			}
		}
	}
	return 0;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	string s, p;
	cin >> s >> p;

	vector<int> table = makeTable(p);
	cout << kmp(s, p, table);
	return 0;
}