백준
백준 소스코드 [C++] 16172 나는 친구가 적다 (Large)
Hani_Levenshtein
2020. 11. 9. 08:14
16172번: 나는 친구가 적다 (Large)
첫 번째 줄에는 알파벳 소문자, 대문자, 숫자로 이루어진 문자열 S가 주어진다. (1 ≤ |S| ≤ 200,000) 두 번째 줄에는 성민이가 찾고자 하는 알파벳 소문자, 대문자로만 이루어진 키워드 문자열 K가
www.acmicpc.net
백준 소스코드 [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;
}