mycod.es

IP 175.209.0.0 Created 08-12 02:35
1
#include <iostream>
2
#include <vector>
3
4
using namespace std;
5
6
const int BIT_SET_SIZE = 50000;
7
8
int word_size = sizeof(void *);
9
10
class bit_set {
11
public:
12
long long size;
13
vector<unsigned long long> bits;
14
static const int ull_size = sizeof(unsigned long long) * 8;
15
16
bit_set(int bit_size) {
17
size = bit_size;
18
bits.resize(bit_size / ull_size + 1);
19
}
20
21
class BitReference {
22
unsigned long long &word;
23
unsigned long long mask;
24
25
public:
26
BitReference(unsigned long long &word, size_t bit_index) : word(word), mask(1ULL << bit_index) {
27
}
28
29
operator bool() const {
30
return (word & mask) != 0;
31
}
32
33
BitReference &operator=(bool val) {
34
if (val) word |= mask;
35
else word &= ~mask;
36
return *this;
37
}
38
};
39
40
41
BitReference operator[](size_t idx) {
42
return BitReference(bits[idx / ull_size], idx % ull_size);
43
}
44
45
bit_set operator|(const bit_set &other) const {
46
bit_set result(*this);
47
size_t size = min(bits.size(), other.bits.size());
48
for (size_t i = 0; i < size; i++) {
49
result.bits[i] |= other.bits[i];
50
}
51
return result;
52
}
53
54
bit_set operator|(const unsigned long long val) const {
55
bit_set result(*this);
56
result.bits[0] |= val;
57
return result;
58
}
59
60
bit_set operator<<(const size_t shift) const {
61
bit_set result(*this);
62
63
size_t word_shift = shift / ull_size;
64
size_t bit_shift = shift % ull_size;
65
66
if (word_shift > 0) {
67
for (int i = (int) result.bits.size() - 1; i >= (int) word_shift; --i) {
68
result.bits[i] = result.bits[i - word_shift];
69
}
70
for (int i = 0; i < word_shift; ++i) {
71
result.bits[i] = 0;
72
}
73
}
74
75
if (bit_shift > 0) {
76
for (size_t i = result.bits.size() - 1; i > 0; --i) {
77
result.bits[i] <<= bit_shift;
78
result.bits[i] |= result.bits[i - 1] >> (ull_size - bit_shift);
79
}
80
result.bits[0] <<= bit_shift;
81
}
82
83
return result;
84
}
85
86
bit_set operator&(const bit_set &other) const {
87
bit_set result(*this);
88
size_t size = min(bits.size(), other.bits.size());
89
for (size_t i = 0; i < size; i++) {
90
result.bits[i] = bits[i] & other.bits[i];
91
}
92
return result;
93
}
94
95
bit_set operator+(const bit_set &other) const {
96
bit_set result(*this);
97
unsigned long long carry = 0ULL;
98
size_t n = bits.size();
99
100
for (int i = 0; i < n; ++i) {
101
unsigned long long a = bits[i];
102
unsigned long long b = (i < other.bits.size()) ? other.bits[i] : 0ULL;
103
104
unsigned long long sum = a + b + carry;
105
106
carry = (sum < a || (carry && (sum == a))) ? 1ULL : 0ULL;
107
108
result.bits[i] = sum;
109
}
110
111
return result;
112
}
113
114
bit_set operator-(const bit_set &other) const {
115
bit_set result(*this);
116
unsigned long long borrow = 0ULL;
117
size_t n = bits.size();
118
119
for (size_t i = 0; i < n; ++i) {
120
unsigned long long a = bits[i];
121
unsigned long long b = (i < other.bits.size()) ? other.bits[i] : 0ULL;
122
123
unsigned long long temp = a - b - borrow;
124
125
borrow = (a < b + borrow) ? 1ULL : 0ULL;
126
127
result.bits[i] = temp;
128
}
129
130
return result;
131
}
132
133
bit_set operator~() const {
134
bit_set result(*this);
135
for (auto& bit : result.bits) {
136
bit = ~bit;
137
}
138
return result;
139
}
140
};
141
142
143
string a, b;
144
145
vector<bit_set> A(26, bit_set(BIT_SET_SIZE));
146
147
int solve() {
148
for (int a_idx = 0; a_idx < a.length(); a_idx++) {
149
A[a[a_idx] - 'A'][a_idx] = true;
150
}
151
152
bit_set B = bit_set(BIT_SET_SIZE);
153
for (int b_idx = 0; b_idx < b.length(); b_idx++) {
154
bit_set X = B | A[b[b_idx] - 'A'];
155
bit_set Y = (B << 1) | 1;
156
B = X & ~(X - Y);
157
}
158
159
int ans = 0;
160
for (int i = 0; i < B.size; ++i)
161
if (B[i] == true) ans++;
162
return ans;
163
}
164
165
int main() {
166
ios_base::sync_with_stdio(false);
167
cin.tie(nullptr);
168
cout.tie(nullptr);
169
170
cin >> a >> b;
171
cout << solve() << endl;
172
}
173