-
Notifications
You must be signed in to change notification settings - Fork 25
/
wildcard.test.cpp
76 lines (69 loc) · 1.81 KB
/
wildcard.test.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
// @brief Wildcard Pattern Matching
#define PROBLEM "https://judge.yosupo.jp/problem/wildcard_pattern_matching"
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("tune=native")
#include "cp-algo/math/fft.hpp"
#include "cp-algo/random/rng.hpp"
#include <bits/stdc++.h>
using namespace std;
using namespace cp_algo::math;
using fft::ftype;
using fft::point;
using fft::cvector;
void semicorr(auto &a, auto &b) {
b.resize(size(a));
a.fft();
b.fft();
a.dot(b);
a.ifft();
}
auto is_integer = [](point a) {
static const double eps = 1e-8;
return abs(imag(a)) < eps
&& abs(real(a) - round(real(a))) < eps;
};
string matches(string const& A, string const& B, char wild = '*') {
static const int sigma = 26;
static point project[2][sigma];
static bool init = false;
if(!init) {
init = true;
for(int i = 0; i < sigma; i++) {
project[0][i] = polar(1., (ftype)cp_algo::random::rng());
project[1][i] = conj(project[0][i]);
}
}
array ST = {&A, &B};
cvector P[2];
for(int i: {0, 1}) {
size_t N = size(*ST[i]);
P[i].resize(N);
for(size_t k = 0; k < N; k++) {
char c = ST[i]->at(k);
size_t idx = i ? N - k - 1 : k;
point val = c == wild ? 0 : project[i][c - 'a'];
P[i].set(idx, val);
}
}
semicorr(P[0], P[1]);
string ans(size(A) - size(B) + 1, '0');
for(size_t j = 0; j < size(ans); j++) {
ans[j] = '0' + is_integer(P[0].get(size(B) - 1 + j));
}
return ans;
}
void solve() {
string a, b;
cin >> a >> b;
cout << matches(a, b) << "\n";
}
signed main() {
//freopen("input.txt", "r", stdin);
ios::sync_with_stdio(0);
cin.tie(0);
int t = 1;
//cin >> t;
while(t--) {
solve();
}
}