백준 소스코드 [C++] 16172 나는 친구가 적다 (Large)

www.acmicpc.net/problem/16172

16172번: 나는 친구가 적다 (Large)

백준 소스코드 [C++] 16172 나는 친구가 적다 (Large)

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

int main() {
	ios_base::sync_with_stdio(false), cin.tie(nullptr);
	string target, sub,real="";
	getline(cin, target);
	getline(cin, sub);
	for (int i = 0;i < target.size();i++) if (!('0' <= target[i] && target[i] <= '9')) real += target[i];
	vector<int> res = kmp(real, sub);
	if (res.size()) cout << "1";
	else cout << "0";
	return 0;
}