🌱 Free Contest 131 - APPEAR

\(\Huge \text{🌱 Free Contest 131 - APPEAR}\)

🔗 Link: https://oj.vnoi.info/problem/fc131_appear

📌 Tags: `String Matching`, `Precalculation`, `Math`

👤 Writer: @SPyofgame

👥 Contributor: @Melonade

📋 Content:

Hướng dẫn
- Tiếp cận
- Code
- Bonus

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ẻ

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

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

SPyofgame Code [1] - Make a simple Brute-force
















































#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;
}

SPyofgame Code [2] - Calculate independently without concatenating string



























































#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

SPyofgame Code [3] - Optimize Brute-forces with Precalculation

































































#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;
}

SPyofgame Code [4] - Split into two simple loops












































































#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

SPyofgame Code [5] - Optimize Brute-forces with Math































































#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;
}

SPyofgame Code [6] - Simplify The Formula




















































#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 ?

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`	在筆記中貼入程式碼
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.

🔗 Link: https://oj.vnoi.info/problem/fc131_appear

📌 Tags: String Matching, Precalculation, Math

👤 Writer: @SPyofgame

👥 Contributor: @Melonade

📋 Content:

Hướng dẫn

Tiếp cận

Code

Bonus

📌 Tags: `String Matching`, `Precalculation`, `Math`