백준 소스코드 [C++] 16916 부분 문자열

www.acmicpc.net/problem/16916

16916번: 부분 문자열

백준 소스코드 [C++] 16916 부분 문자열

#include <iostream>
#include <algorithm>
#include <queue>
#include <string.h>
#include <limits.h>
#include <vector>
#include <math.h>
#include <stack>
#include <bitset>
typedef long long ll;
using namespace std;
vector<int> getPi(string sub) {
	vector<int> pi(sub.size(), 0);
	for (int i = 1, j = 0; i < sub.size(); i++) {
		while (j > 0 && sub[i] != sub[j]) j = pi[--j];
		if (sub[i] == sub[j]) pi[i] = ++j;
	}
	return pi;
}
void kmp(string target, string sub) {

	vector<int> pi = getPi(sub);
	for (int i = 0, j = 0; i < target.size(); i++) {
		while (j > 0 && target[i] != sub[j]) j = pi[--j];
		if (target[i] == sub[j]) {
			if (j+1 == sub.size()) {
				cout << "1";
				return;
			}
			else j++;
		}
	}
	cout << "0";
	return;
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(nullptr);
	string target, sub;
	cin >> target;
	cin >> sub;
	kmp(target, sub);
	return 0;
}