\(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.99}}}}}\)

\(\color{#008b8b}{\text{Hướng dẫn}}\)

• Nhận xét rằng điều kiên đề cần thỏa là \((0 < j - i \leq k)\) và \((|s_i| = |s_j|)\). Nên ta không quan tâm tới xâu kí tự mà chỉ quan tâm độ dài của nó

• Với mỗi độ dài \(t\). Ta duyệt qua các cặp vị trí \((i < j)\) thỏa \((|s_i| = |s_j| = t)\) và kiểm tra xem \((0 < j - i \leq k)\) thì tăng biến đếm

• Nhận xét rằng nếu các giá trị \(a_{i_1}, a_{i_2}, \dots, a_{i_k}\) có cung độ dài thì nếu \(a_l\) và \(a_r\) thỏa thì cặp nằm giữa vị trí \([l, r]\) đều thỏa

Nếu với mỗi tập gồm các vị trí có cùng độ dài, từ vị trí \(l\), tìm được \(r \leq\) lớn nhất thỏa mãn các điều kiện thì tổng \(\Sigma(r - l)\) là kết quả cần tìm

\(\color{#008b8b}{\text{Tiếp cận: Hai con trỏ}}\)

• Gọi vector \(a[t]\) chứa vị trí các xâu có độ dài \(t\), theo thứ tự tăng dần

Duyệt \(i = 1 \rightarrow n\), thêm vị trí \(i\) vào \(a\Big[|s_i|\Big]\), lúc này vì \(i\) tăng dần nên các tập \(a[]\) cũng có giá trị trong tập tăng dần

• Duyệt qua các giá trị \(t\). Và với mỗi vị trí \(l\) trong tập \(a[t]\), ta tìm vị trí \(r\) lớn nhất mà cặp \(a_l\) và \(a_r\) thỏa đề, rồi cộng vào kết quả giá trị \(r - l\)

Không mất tính tổng quát giả sử với mỗi vị trí \(t\) và các vị trí cố định \(l\), thì khi \(r\) là vị trí thỏa mãn thì các cặp \((l, p)\) với \(l < p \leq r\) là các cặp thỏa mãn cần tìm.

Nhờ điều kiện không mất tính tổng quát ban đầu nên việc đếm kiểu này đảm bảo đếm đủ và không trùng nhau.

\(\color{#008b8b}{\text{Độ phức tạp}}\)

• Nhận dữ liệu mất \(O(n \times max(|s|)\)

• Duyệt qua các \(t\) mất \(O(t) = O(max(|s|))\)

• Duyệt qua các vị trí \(l\), tìm vị trí \(r\) lớn nhất thỏa mãn mất \(O(n)\)

\(\color{#008b8b}{\text{Code tham khảo }}\): Hai con trỏ

\(^{^{\color{purple}{\text{Độ phức tạp : }} O(n \times max(|s|))\ \color{purple}{\text{thời gian}}\ ||\ O(n + max(|s|))\ \color{purple}{\text{bộ nhớ}}}}\)

#include <iostream>
#include <vector>

using namespace std;

vector<int> a[22];
int main()
{
    int n, k;
    cin >> n >> k;

    for (int i = 0; i < n; ++i)
    {
        string s;
        cin >> s;
        a[s.size()].push_back(i);
    }

    long long res = 0;
    for (int s = 2; s <= 20; ++s)
    {
        for (int l = 0, r = 0; r < a[s].size(); ++r)
        {
            while (a[s][r] - a[s][l] > k) ++l;
            res += r - l;
        }
    }

    cout << res;
    return 0;
}

\(\color{#008b8b}{\text{Code tham khảo }}\): Hai con trỏ

\(^{^{\color{purple}{\text{Độ phức tạp : }} O(n \times max(|s|))\ \color{purple}{\text{thời gian}}\ ||\ O(n + max(|s|))\ \color{purple}{\text{bộ nhớ}}}}\)

#include <iostream>

using namespace std;

const int LIM = 3e5 + 35;
int a[LIM];
int cnt[22];
int main()
{
    int n, k;
    cin >> n >> k;

    long long res = 0;
    for (int l = 1 - k, r = 1; r <= n; ++l, ++r)
    {
        string s;
        cin >> s;
        a[r] = s.size();

        res += cnt[a[r]]++;
        if (l > 0) --cnt[a[l]];
    }

    cout << res;
    return 0;
}