1786 : 찾기

풀이

KMP

룰루랄라

코드

#include <stdio.h>
#include <vector>
#include <string.h>
using namespace std;

const int N_ = 1e6 + 5;

int fail[N_], t_len, p_len;
char T[N_], P[N_];

int main() {
	gets_s(T); t_len = strlen(T);
	gets_s(P); p_len = strlen(P);

	for (int i = 1, j = 0; i < p_len; ++i) {
		while (j && P[i] != P[j]) j = fail[j - 1];
		if (P[i] == P[j]) fail[i] = ++j;
	}

	vector<int> ans;
	for (int i = 0, j = 0; i < t_len; ++i) {
		while (j && T[i] != P[j]) j = fail[j - 1];

		if (T[i] == P[j]) {
			if (j == p_len - 1) {
				ans.push_back(i - p_len + 2);
				j = fail[j];
			}
			else ++j;
		}
	}

	printf("%d\n", ans.size());
	for (auto p : ans) printf("%d ", p);

	return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2017-02-28 16:26

Read more posts by this author