백준 16916 부분 문자열

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

16916번: 부분 문자열

 

신촌 알고리즘 초급반 2주차 연습문제!

 

<문제>

 

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

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

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

 

<입력>

 

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

 

<출력>

 

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

 

<풀이>

 

처음에는 이번주차 강의에서 배운 Polynomial Rolling hash 를 통해서 풀어보려고 접근했다.

 

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <cmath>
#include <iostream>
#include <vector>
#include <algorithm>
#include <memory.h>
#include <string>

using namespace std;
using ll = long long;

string S, pattern;
ll poly_s = 0, poly_p = 0;

int main(void) {

	ll k = 1;

	getline(cin, S);
	getline(cin, pattern);

	if (S.size() < pattern.size()) {
		printf("0"); return 0;
	}

	for (size_t i = 0; i < pattern.size(); i++) {
		poly_p += k * (pattern[i] - 'a' + 1);
		poly_s += k * (S[i] - 'a' + 1);
		k *= 27;
	}
	k /= 27;

	for (size_t i = pattern.size(); i < S.size(); i++) {
		if (poly_p == poly_s) {
			break;
		}
		poly_s -= (S[i - pattern.size()] - 'a' + 1);
		poly_s = poly_s / 27;
		poly_s += k * (S[i] - 'a' + 1);
	}

	if (poly_p == poly_s)
		printf("1");
	else
		printf("0");

	return 0;
}

 

그런데 입력에 들어오는 문자열의 길이가 최대 100만까지 들어올 수 있기 때문에, k의 값이 27이 99만.. 제곱까지 가면 long long의 범위를 넘어서서 백준 채점 10프로 정도에서 틀렸습니다 가 나와서 다른 알고리즘으로 접근하기로 했다.

 

문자열 비교에 굉장히 유명한 알고리즘인데, KMP 알고리즘이다.

이 알고리즘은 패턴으로 주어지는 문자열의 내부 정보를 먼저 계산해서 불필요한 비교를 건너뛰는 알고리즘이다.

 

물론 이렇게 이야기하면 바로 이해하기 어렵겠으니, 예시를 같이 들자면

만약 우리가 pat = abcabcacab 라는 문자열을 받았다고 하면, 이 패턴을 어떤 문자열과 비교하다가 

abcabc 에서 실패하는 경우, 처음 문자열부터 다시 비교할 필요가 있을까?

abcabc 를 통과했다는 의미는 앞에 abc는 당연히 비교할 필요가 없다는 이야기 아닐까?

 

라는 아이디어를 가지고 만들어진 알고리즘이다. 문제는 그래서 코드를 작성하지? 일 것이다. 

 

먼저 실패함수라는 개념을 패턴에 적용해서 패턴 사이에 접두사와 현재 보고 있는 패턴의 원소까지의 관계 (접미사)를 비교해서 저장할 필요가 있다.

 

패턴의 원소를 pn이라고 할 때,  p0p1p2 ... pi = p(j-i)...pj 인, i>=0 이 존재하는 경우, 가장 큰 i < j 를 우리는 f(j)라고 할 수 있고, 존재하지 않을 경우, f(j) = -1 이다. 

 

이렇게 패턴 내부의 접미사와 접두사를 비교해서 비교 실패시 다음 비교 원소(패턴 내부의) 를 효율적으로 알려줄 수 있고, 이렇게 하면 기존 O(nm) 에서 O(n+m)으로 개선할 수 있다.

 

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <cmath>
#include <iostream>
#include <vector>
#include <algorithm>
#include <memory.h>
#include <string>

using namespace std;
using ll = long long;

string S, pattern;
vector <int> failure;

void fail(string pat) {
	int i, j;
	int n = pat.size();
	failure.push_back(-1);
	for (j = 1; j < n; j++) {
		i = failure[j - 1]; // 지금까지 구해놓은 failure 배열의 정보를 이용
		while ((pat[j] != pat[i + 1]) && (i >= 0)) {
			// 현재 j번째 패턴의 문자와 i+1 번째 문자를 비교해서
			// 다른 경우, 이전에 구해 놓은 failure vector를 통해서 
			// 다음 검사할 문자로 이동한다.
			i = failure[i];
		}
		if (pat[j] == pat[i + 1]) {
			failure.push_back(i + 1);
			//failure[j] = i + 1;
			// j번째 문자 검사하다가 틀리면 i+1 번째 원소로 이동
		}
		else failure.push_back(-1);
	}
}

int main(void) {

	ll k = 1;

	int i = 0, j = 0, n, m;
	getline(cin, S);
	getline(cin, pattern);

	n = S.size();
	m = pattern.size();
	if (n < m) {
		printf("0"); return 0;
	}

	fail(pattern);

	while (i < n && j < m) {
		if (S[i] == pattern[j]) {
			i++; j++;
		}
		else if (j == 0) {
			i++;
		}
		else {
			// 패턴의 failure 정보를 이용해서
			// 중간 지점 부터 검사
			j = failure[j - 1] + 1;
		}
	}
	if (j == m) printf("1");
	else printf("0");

	return 0;
}