owned this note
owned this note
Published
Linked with GitHub
---
tags: VNOJ, Free Contest, String Matching, Precalculation, Math, SPyofgame
title: 🌱 Free Contest 131 - APPEAR
author: Editorial-Slayers Team
license: Public domain
---
<style>
.markdown-body { max-width: 2048px; }
</style>
$\Huge \text{🌱 Free Contest 131 - APPEAR}$
-----
###### 🔗 Link: [https://oj.vnoi.info/problem/fc131_appear](https://oj.vnoi.info/problem/fc131_appear)
###### 📌 Tags: `String Matching`, `Precalculation`, `Math`
###### 👤 Writer: @SPyofgame
###### 👥 Contributor: [@Melonade](https://codeforces.com/profile/Melonade)
###### 📋 Content:
[TOC]
-----
## Hướng dẫn
Nhận thấy rằng việc tính toán hàm $F(T, S_i + S_j)$ có thể được chia làm $2$ phần:
- $1$ phần kết quả giữa hậu tố của $S_i$ và tiền tố của $T$.
- $1$ phần kết quả giữa tiền tố của $S_j$ và hậu tố của $T$.
Ta định nghĩa:
- $suff(i, x) = \{0/1\}$ là kết quả (khác nhau / bằng nhau) của việc so sánh giữa $2$ xâu con có độ dài $x$ là hậu tố của $S_i$ và tiền tố của $T$.
- $pref(j, x) = \{0/1\}$ là kết quả (khác nhau / bằng nhau) của việc so sánh giữa $2$ xâu con có độ dài $x$ là tiền tố của $S_j$ và hậu tố của $T$.
- $cntsuff(x) = \overset{n}{\underset{i = 1}{\Large \Sigma}} suff(i, x)$, là số xâu $S_i$ có hậu tộ độ dài $x$ bằng tiền tố độ dài $x$ của $T$.
- $cntpref(x) = \overset{n}{\underset{j = 1}{\Large \Sigma}} pref(i, x)$, là số xâu $S_j$ có tiền tộ độ dài $x$ bằng hậu tố độ dài $x$ của $T$.
Lúc này ta có: $\overset{n}{\underset{i = 1}{\Large \Sigma}} \overset{n}{\underset{j = 1}{\Large \Sigma}} F(T, S_i + S_j)
\\=
\overset{n}{\underset{i = 1}{\Large \Sigma}} \overset{n}{\underset{j = 1}{\Large \Sigma}} F(T, S_i) + \overset{n}{\underset{i = 1}{\Large \Sigma}} \overset{n}{\underset{j = 1}{\Large \Sigma}} \overset{|t|}{\underset{x = 1}{\Large \Sigma}} \left ( suff(i, x) \times pref(i, |t| - x) \right )
\\=
2n \times \overset{n}{\underset{i = 1}{\Large \Sigma}} F(T, S_i) + \overset{|t|}{\underset{x = 1}{\Large \Sigma}} \left ( \overset{n}{\underset{i = 1}{\Large \Sigma}} pref(i, x) \times \overset{n}{\underset{i = 1}{\Large \Sigma}} suff(i, |t| - x) \right )
\\=
2n \times \overset{n}{\underset{i = 1}{\Large \Sigma}} F(T, S_i) + \overset{|t|}{\underset{x = 1}{\Large \Sigma}} \LARGE \left ( \normalsize cntsuff(x) \times cntpref(|t| - x) \LARGE \right )$
Vậy bằng việc tiền xử lí và toán, ta có thể tính kết quả đủ nhanh.
-----
### Tiếp cận
Tại **Code[1]**:
Đầu tiên mình sẽ viết một thuật toán trâu đơn giản: Cứ mỗi một cặp xâu $(s_i, s_j)$ thì mình nối xâu và đếm số xâu con $t$ có trong đó.
Tại **Code[2]**:
Mình cần tính toán từng thàn phần một cách riêng biệt nhằm bỏ vòng for $O(n^2)$ kia đi. Do đó mình không dùng phép nối xâu, mà tính cho từng cái một, mỗi cái ở một nửa kia.
Tại **Code[3]**:
Mình nhận thấy là cứ mỗi vòng for mình lại tính một phần có kết quả giống nhau, cho nên mình sẽ tiền xử lí và lưu trữ các giá trị này trước.
Tại **Code[4]**:
Vì vòng for trên rất phức tạp, nên mình sẽ chia làm 2 phần vòng for đơn giản. Điều này tạo điều kiện cho việc tính toán kết quả một cách đơn giản hơn.
Tại **Code[5]**:
Mình nhận thấy là ta lại tính đi tính lại các phần có kết quả giống nhau. Vì vậy mình lại tiền xử lí tiếp đoạn này và sử dụng toán để tính trong $O(1)$.
Tại **Code[6]**:
Giờ mình chỉ cần đơn giản hóa vấn đề và rút gọn công thức .
Bài toán này cũng chỉ có thế thôi, chúc bạn một ngày vui vẻ :thumbsup:
-----
### Code
> For $p = |t|$
> For $q = max(|S_i|)$
> **Time:** $O(p \times n^2 \times q)$
> **Space:** $O(p + n \times q)$
> **Algo:** String Matching, Brute-forces
> [color=lightgreen]
:::success
:::spoiler SPyofgame Code [1] - Make a simple Brute-force
```cpp=
#include <iostream>
#include <cstring>
using namespace std;
const int LIM = 2e5 + 25;
int n;
string t;
string s[LIM];
int main()
{
/// Fast Input
ios::sync_with_stdio(NULL);
cin.tie(NULL);
/// Input
cin >> t;
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> s[i];
/// Calculating
int res = 0;
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= n; ++j)
{
/// For each pair $(s_i, s_j)$ we concat two strings together
string u = s[i] + s[j];
int p = t.size();
int q = u.size();
/// Calculate the number of times $t$ appears in $u$
int cnt = 0;
for (int l = 0, r = p; r <= q; ++l, ++r)
if (t == u.substr(l, p))
++cnt;
/// Add current count to the result
res += cnt;
}
}
/// Output
cout << res;
return 0;
}
```
:::
:::success
:::spoiler SPyofgame Code [2] - Calculate independently without concatenating string
```cpp=
#include <iostream>
#include <cstring>
using namespace std;
const int LIM = 2e5 + 25;
int n;
string t;
string s[LIM];
int main()
{
/// Fast Input
ios::sync_with_stdio(NULL);
cin.tie(NULL);
/// Input
cin >> t;
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> s[i];
/// Calculating
int res = 0;
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= n; ++j)
{
int p = t.size();
int qi = s[i].size();
int qj = s[j].size();
int cnti = 0;
for (int l = 0, r = p; r <= qi; ++l, ++r)
if (t == s[i].substr(l, p))
++cnti;
int cntj = 0;
for (int l = 0, r = p; r <= qj; ++l, ++r)
if (t == s[j].substr(l, p))
++cntj;
res += cnti + cntj;
for (int x = 1, y = t.size() - 1; x <= t.size(); ++x, --y)
{
int pref = (y < 1 || y > qj) ? 0 : (t.substr(p - y) == s[j].substr(0, y));
int suff = (x < 1 || x > qi) ? 0 : (t.substr(0, x) == s[i].substr(qi - x));
if (suff && pref)
{
++res;
}
}
}
}
/// Output
cout << res;
return 0;
}
```
:::
> For $p = |t|$
> For $q = max(|S_i|)$
> **Time:** $O(p \times n^2 + n \times q + n \times min(p, q)^2)$
> **Space:** $O(p + n \times q)$
> **Algo:** String Matching, Precalculation, Brute-forces
> [color=lightgreen]
:::success
:::spoiler SPyofgame Code [3] - Optimize Brute-forces with Precalculation
```cpp=
#include <iostream>
#include <cstring>
using namespace std;
const int LIM = 2e5 + 25;
int n;
string t;
string s[LIM];
bool suff[LIM][22]; /// suff[i][x] = true <=> suffix of size (x) of (s[i]) = prefix of size (x) of (t[])
bool pref[LIM][22]; /// pref[i][x] = true <=> prefix of size (x) of (s[i]) = suffix of size (x) of (t[])
int cnt[LIM];
int main()
{
/// Fast Input
ios::sync_with_stdio(NULL);
cin.tie(NULL);
/// Input
cin >> t;
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> s[i];
/// Precalculating
for (int i = 1; i <= n; ++i)
{
int p = t.size();
int q = s[i].size();
memset(pref[i], 0, sizeof(pref[i]));
memset(suff[i], 0, sizeof(suff[i]));
for (int x = 1; x <= min(p, q); ++x)
{
pref[i][x] = (t.substr(p - x) == s[i].substr(0, x));
suff[i][x] = (t.substr(0, x) == s[i].substr(q - x));
}
cnt[i] = 0;
for (int l = 0, r = p; r <= q; ++l, ++r)
if (t == s[i].substr(l, p))
++cnt[i];
}
/// Calculating
int res = 0;
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= n; ++j)
{
res += cnt[i] + cnt[j];
for (int x = 1, y = t.size() - 1; x <= t.size(); ++x, --y)
{
if (suff[i][x] && pref[j][y])
{
++res;
}
}
}
}
/// Output
cout << res;
return 0;
}
```
:::
:::success
:::spoiler SPyofgame Code [4] - Split into two simple loops
```cpp=
#include <iostream>
#include <cstring>
using namespace std;
const int LIM = 2e5 + 25;
int n;
string t;
string s[LIM];
bool suff[LIM][22]; /// suff[i][x] = true <=> suffix of size (x) of (s[i]) = prefix of size (x) of (t[])
bool pref[LIM][22]; /// pref[i][x] = true <=> prefix of size (x) of (s[i]) = suffix of size (x) of (t[])
int cnt[LIM];
int main()
{
/// Fast Input
ios::sync_with_stdio(NULL);
cin.tie(NULL);
/// Input
cin >> t;
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> s[i];
/// Precalculating
for (int i = 1; i <= n; ++i)
{
int p = t.size();
int q = s[i].size();
memset(pref[i], 0, sizeof(pref[i]));
memset(suff[i], 0, sizeof(suff[i]));
for (int x = 1; x <= min(p, q); ++x)
{
pref[i][x] = (t.substr(p - x) == s[i].substr(0, x));
suff[i][x] = (t.substr(0, x) == s[i].substr(q - x));
}
cnt[i] = 0;
for (int l = 0, r = p; r <= q; ++l, ++r)
if (t == s[i].substr(l, p))
++cnt[i];
}
/// Calculating in same pair
int res = 0;
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= n; ++j)
{
res += cnt[i] + cnt[j];
}
}
/// Calculating in diff pair
for (int x = 0, y = t.size(); x <= t.size(); ++x, --y)
{
for (int i = 1; i <= n; ++i)
{
if (suff[i][x])
{
for (int j = 1; j <= n; ++j)
{
if (pref[j][y])
{
++res;
}
}
}
}
}
/// Output
cout << res;
return 0;
}
```
:::
> For $p = |t|$
> For $q = max(|S_i|)$
> **Time:** $O(p + n \times q + n \times min(p, q)^2)$
> **Space:** $O(p + n \times q)$
> **Algo:** String Matching, Precalculation, Math
> [color=lightgreen]
:::success
:::spoiler SPyofgame Code [5] - Optimize Brute-forces with Math
```cpp=
#include <iostream>
#include <cstring>
using namespace std;
const int LIM = 2e5 + 25;
int n;
string t;
string s[LIM];
bool suff[LIM][22]; /// suff[i][x] = true <=> suffix of size (x) of (s[i]) = prefix of size (x) of (t[])
bool pref[LIM][22]; /// pref[i][x] = true <=> prefix of size (x) of (s[i]) = suffix of size (x) of (t[])
int cntpref[22];
int cntsuff[22];
int cnt[LIM];
int main()
{
/// Fast Input
ios::sync_with_stdio(NULL);
cin.tie(NULL);
/// Input
cin >> t;
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> s[i];
/// Precalculating
long long res = 0;
memset(cntpref, 0, sizeof(cntpref));
memset(cntsuff, 0, sizeof(cntsuff));
for (int i = 1; i <= n; ++i)
{
int p = t.size();
int q = s[i].size();
memset(pref[i], 0, sizeof(pref[i]));
memset(suff[i], 0, sizeof(suff[i]));
for (int x = 1; x <= min(p, q); ++x)
{
pref[i][x] = (t.substr(p - x) == s[i].substr(0, x));
suff[i][x] = (t.substr(0, x) == s[i].substr(q - x));
cntpref[x] += pref[i][x];
cntsuff[x] += suff[i][x];
}
cnt[i] = 0;
for (int l = 0, r = p; r <= q; ++l, ++r)
if (t == s[i].substr(l, p))
++cnt[i];
}
/// Calculating in same pair
for (int i = 1; i <= n; ++i)
res += 2LL * cnt[i] * n;
/// Calculating in diff pair
for (int x = 0, y = t.size(); x <= t.size(); ++x, --y)
res += 1LL * cntpref[y] * cntsuff[x];
/// Output
cout << res;
return 0;
}
```
:::
:::success
:::spoiler SPyofgame Code [6] - Simplify The Formula
```cpp=
#include <iostream>
#include <cstring>
using namespace std;
const int LIM = 2e5 + 25;
int n;
string t;
string s[LIM];
int cntpref[22];
int cntsuff[22];
int main()
{
/// Fast Input
ios::sync_with_stdio(NULL);
cin.tie(NULL);
/// Input
cin >> t;
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> s[i];
/// Precalculating
long long res = 0;
memset(cntsuff, 0, sizeof(cntsuff));
memset(cntpref, 0, sizeof(cntpref));
for (int i = 1; i <= n; ++i)
{
int p = t.size();
int q = s[i].size();
for (int x = 1; x <= min(p, q); ++x)
{
cntpref[x] += (t.substr(p - x) == s[i].substr(0, x));
cntsuff[x] += (t.substr(0, x) == s[i].substr(q - x));
}
/// Calculating in same pair
for (int l = 0, r = p; r <= q; ++l, ++r)
if (t == s[i].substr(l, p))
res += n + n;
}
/// Calculating in diff pair
for (int x = 0, y = t.size(); x <= t.size(); ++x, --y)
res += 1LL * cntpref[y] * cntsuff[x];
/// Output
cout << res;
return 0;
}
```
:::
-----
### Bonus
Với $p = |t|$ và $q = max(|S_i|)$
$1.$ Giả sử $|s_i|$ và $|t|$ có thể rất lớn:
- Bạn có thể giải trong $O(p + n \times q + n \times min(p, q)^{1.5})$ không ?
- Bạn có thể giải trong $O(p + n \times q + n \times min(p, q) \log min(p, q))$ không ?
- Bạn có thể giải trong $O(p + n \times q + n \times min(p, q))$ không ?
$2.$ Giả sử có $q$ truy vấn $t_q$:
- Bạn có thể giải nhanh hơn $O(q \times (p + n \times q + n \times min(p, q)))$ không ?
- Nếu mọi xâu đều chỉ gồm $2$ kí tự khác nhau thì bạn có thể giải trong bao lâu ?