-
[BOJ] 16172 : 나는 친구가 적다 (Large)
16172 : 나는 친구가 적다 (Large) 풀이 kmp 잘 짜주면 된다. 코드 #include <iostream> #include <string> using namespace std; int fail[200022]; string a, t, p; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> a >> p; for (auto it : a) if (it < '0' || it > '9') t.push_back(it); for (int i = 1, j = 0; i < p.length(); ++i) { while (j && p[i] != p[j]) j = fail[j - 1]; if (p[i]...
-
[BOJ] 16171 : 나는 친구가 적다 (Small)
16171 : 나는 친구가 적다 (Small) 풀이 잘 짜주면 된다. 근데 그냥 16172번 복붙했다. 코드 #include <iostream> #include <string> using namespace std; int fail[200022]; string a, t, p; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> a >> p; for (auto it : a) if (it < '0' || it > '9') t.push_back(it); for (int i = 1, j = 0; i < p.length(); ++i) { while (j && p[i] != p[j]) j = fail[j -...
-
[BOJ] 11585 : 속타는 저녁 메뉴
11585 : 속타는 저녁 메뉴 풀이 원순열을 구현하려면 귀찮으니까 똑같은 문자열을 두 번 이어붙여주자 그리고 kmp를 돌려서 substring으로 등장하는 횟수를 구해주자 코드 #include <cstdio> const int n_ = 1e6 + 5; int gcd(int a, int b) { return b ? gcd(b, a%b) : a; } int n, i, j, cnt, fail[n_]; char a[n_], b[n_ * 2]; int main() { scanf("%d", &n); for (i = 0; i < n; i++) scanf(" %c", &a[i]); for (i =...
-
[BOJ] 1786 : 찾기
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;...