Hướng dẫn cho Eticket (DHBB 2021 T.Thử)


Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: SPyofgame


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


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

  • Ta chia bài toán làm 3 công đoạn để xử lí như sau

  • Công đoạn 1: Nhập tất cả xâu từ điển, một hàm khởi tạo cấu trúc dữ liệu \(i(s)\) một hàm \(f(s)\) kiểm tra tồn tại của xâu \(s\) có trong từ điển ko

  • Công đoạn 2: Nhập tất cả xâu nhãn dán, môt hàm tiền xử lí xâu \(c(s)\) một hàm quay xâu \(r(s)\), một hàm xóa kí tự đầu/cuối trong xâu \(d(s)\), một hàm hợp hai xầu ở đầu/cuối \(m(s)\), hàm kiểm tra toàn bộ \(q(s)\) đoạn xâu con \(s_1, s_2, \dots, s_{q(s)}\) bằng hàm \(v(s)\) (Với \(s_1 + s_2 + \dots + s_{q(s)} = s\))

  • Công đoạn 3: Xử lí tính toán và kiểm tra \(s(t)\) lần quay thứ \(t\). Và xuất kết quả bằng hàm \(e(s)\)


\(\color{#008b8b}{\text{Tiếp cận}}\)

  • Vì đề yêu cầu ta phải kiểm tra xem các xâu trong nhãn dán có trong từ điển không

Nên ta cần một hàm để kiểm tra tính tồn tại của một xâu \(s\) có trong từ điển hay không là hàm \(f(s)\) ("f = found ?")

Tuy nhiên để kiểm tra tốt hơn ta cần dùng cấu trúc dữ liệu đặc biệt tự viết \(i(s)\) ("i = initialization")

  • Ta cần phải kiểm tra thử \(t\) vị trí, tại lần quay thứ \(t\) ta kiểm tra xem nó thỏa hay không

Nhưng thay vì lần \(t\) quay \(t\) lần, ta tối ưu bằng cách mỗi lần kiểm tra vị trí \(0 \leq t < k\) xong thì ta mới quay toàn bộ xâu. Ta cần một hàm \(r(s)\) để quay xâu ("r = rotate")

Tuy nhiên xâu là cấu trúc dữ liệu không tốt trong trường hợp này, ta sẽ đổi sang cấu trúc dữ liệu đặc biệt tự viết để tối ưu hơn, quá trình tiền xử lí bằng hàm \(c(s)\) ("c = construct")

  • Quay xâu một lần

Hàm \(q(s)\) cho biết số xâu con trong xâu \(s\) (để tính độ phức tạp)

Ta cần hàm \(d(s)\) xóa một kí tự ở đầu hoặc cuối ("d = delete")

Ta cần hàm \(m(s)\) để hợp nhất kí tự đó với xâu đằng xâu, trước ("m = merge")

Ta cần hàm \(v(s)\) để xác định xem xâu có chứa các xâu con có thuộc từ điển không.Để tiện thì các xâu chỉ chứa ('.') cũng coi là trong từ điển ("v = valid")

  • Sau đó ta xử lí tính toán và xuất kết quả

Dùng mảng đánh dấu để xác định lần quay thứ \(t\) có thỏa hay không bằng hàm \(s(t)\) ("s = solve")

Và xuất số lượng kết quả và các kết quả \(t\) thỏa mãn bằng hàm \(e(s)\) ("e = extract")


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

  • Mảng của xâu

Nhập xâu \(O(n \times k) + O(m \times k)\)

Khởi tạo \(O(i(s)) = O(n \times k)\)

Truy vấn \(O(f(s)) = O(n \times |s|)\)

Xác định \(O(v(s)) = O(\Sigma(f(s_i))) = O(q(s) \times \frac{k}{q(s)} \times n)\)

Không cần tiền xử lí xâu \(O(c(s)) = 0\)

Quay xâu \(O(r(s)) = O(k)\)

Xóa kí tự \(O(d(s)) = O(k)\)

Hợp hai xâu \(O(m(s)) = O(k)\)

Kiểm tra \(O(s(t)) = O(O(r(s)) + O(d(s)) + O(m(s))) + O(v(s)) \times m) = O(n \times m \times k)\)

Xuất kết quả \(O(e(s)) = O(k)\)

Kết quả \(res = O(n \times k) + O(m \times k) + O(i(s)) + O(c(s)) \times m + k \times O(s(t)) + O(e(s)) = O(n \times m \times k^2)\)

Lợi ích: Hằng số nhỏ, Dễ cài, Code ngắn

Trạng thái: Quá thời gian


  • Mảng xâu đã sắp xếp và hàng đợi hai đầu chứa kí tự

Tối ưu: Dùng mảng sắp xếp để tìm kiếm bằng chặt nhị phân

Tối ưu: Dùng hàng đợi để thêm xóa kí tự cuối nhanh hơn

Nhập xâu \(O(n \times k) + O(m \times k)\)

Khởi tạo \(O(i(s)) = O(n \times log(n) \times k)\)

Truy vấn \(O(f(s)) = O(log(n) \times |s|)\)

Xác định \(O(v(s)) = O(\Sigma(f(s_i))) = O(q(s) \times \frac{k}{q(s)} \times log(n))\)

Tiền xử lí \(O(c(s)) = O(k)\)

Quay xâu \(O(r(s)) = O(1)\)

Xóa kí tự \(O(d(s)) = O(1)\)

Hợp hai xâu \(O(m(s)) = O(1)\)

Kiểm tra \(O(s(t)) = O(O(r(s)) + O(d(s)) + O(m(s))) + O(v(s)) \times m) = O(log(n) \times m \times k)\)

Xuất kết quả \(O(e(s)) = O(k)\)

Kết quả \(res = O(n \times k) + O(m \times k) + O(i(s)) + O(c(s)) \times m + k \times O(s(t)) + O(e(s)) = O(log(n) \times k \times (n + m \times k))\)

Lợi ích: Độ phức tạp khá hơn, Hằng số nhỏ, Dễ cài, Code khá ngắn

Trạng thái: Quá thời gian


  • Trie map và hàng đợi hai đầu kí tự (alp là số kí tự khác nhau trong xâu)

Tối ưu: Dùng trie để tìm kiếm không cần chặt nhị phân

Tối ưu: Dùng map để tối ưu bộ nhớ

Nhập xâu \(O(n \times k) + O(m \times k)\)

Khởi tạo \(O(i(s)) = O(n \times k)\)

Truy vấn \(O(f(s)) = O(alp \times |s|)\)

Xác định \(O(v(s)) = O(\Sigma(f(s_i))) = O(q(s) \times \frac{k}{q(s)} \times alp)\)

Tiền xử lí \(O(c(s)) = O(k)\)

Quay xâu \(O(r(s)) = O(1)\)

Xóa kí tự \(O(d(s)) = O(1)\)

Hợp hai xâu \(O(m(s)) = O(1)\)

Kiểm tra \(O(s(t)) = O(O(r(s)) + O(d(s)) + O(m(s))) + O(v(s)) \times m) = O(alp \times m \times k)\)

Xuất kết quả \(O(e(s)) = O(k)\)

Kết quả \(res = O(n \times k) + O(m \times k) + O(i(s)) + O(c(s)) \times m + k \times O(s(t)) + O(e(s)) = O(k \times (n + alp \times m \times k))\)

Lợi ích: Độ phức tạp khá hơn, Dễ cài, Code khá ngắn

Trạng thái: Quá thời gian


  • Trie 2D và hàng đợi hai đầu kí tự (alp là số kí tự khác nhau trong xâu)

Tối ưu: Khai bảo trước trie 2D để tăng tốc độ thời gian

Nhập xâu \(O(n \times k) + O(m \times k)\)

Khởi tạo \(O(i(s)) = O(alp \times n \times k)\)

Truy vấn \(O(f(s)) = O(|s|)\)

Xác định \(O(v(s)) = O(\Sigma(f(s_i))) = O(q(s) \times \frac{k}{q(s)})\)

Tiền xử lí \(O(c(s)) = O(k)\)

Quay xâu \(O(r(s)) = O(1)\)

Xóa kí tự \(O(d(s)) = O(1)\)

Hợp hai xâu \(O(m(s)) = O(1)\)

Kiểm tra \(O(s(t)) = O(O(r(s)) + O(d(s)) + O(m(s))) + O(v(s)) \times m) = O(m \times k)\)

Xuất kết quả \(O(e(s)) = O(k)\)

Kết quả \(res = O(n \times k) + O(m \times k) + O(i(s)) + O(c(s)) \times m + k \times O(s(t)) + O(e(s)) = O(k \times (alp \times n + m \times k))\)

Lợi ích: Độ phức tạp khá hơn, Dễ cài, Code khá ngắn

Trạng thái: Quá thời gian, Tràn bộ nhớ


  • Polynomial-Hashing và hàng đợi hai đầu chứa kí tự (\(Z\) là số lượng hash)

Tối ưu: Dùng hash để so sánh hai đoạn xâu nhanh hơn

Nhập xâu \(O(n \times k) + O(m \times k)\)

Khởi tạo \(O(i(s)) = O(Z \times n \times k \times log(MOD))\)

Truy vấn \(O(f(s)) = O(Z \times log(MOD) \times log(n) \times |s|)\)

Xác định \(O(v(s)) = O(\Sigma(f(s_i))) = O(q(s) \times \frac{k}{q(s)} \times Z \times log(MOD) \times log(n))\)

Tiền xử lí \(O(c(s)) = O(Z \times k)\)

Quay xâu \(O(r(s)) = O(Z \times log(MOD))\)

Xóa kí tự \(O(d(s)) = O(Z \times log(MOD))\)

Hợp hai xâu \(O(m(s)) = O(Z \times log(MOD))\)

Kiểm tra \(O(s(t)) = O(O(r(s)) + O(d(s)) + O(m(s))) + O(v(s)) \times m) = O(Z \times log(MOD) \times log(n) \times k \times m)\)

Xuất kết quả \(O(e(s)) = O(k)\)

Kết quả \(res = O(n \times k) + O(m \times k) + O(i(s)) + O(c(s)) \times m + k \times O(s(t)) + O(e(s)) = O(Z \times log(MOD) \times k \times (n \times + Z \times log(MOD) \times log(n) \times k \times m))\)

Lợi ích: Độ phức tạp khá hơn

Trạng thái: Quá thời gian, Sai với test kháng hash khi \(Z\) nhỏ


  • Polynomial-Hashing và hàng đợi hai đầu chứa hash (\(Z\) là số lượng hash)

Tối ưu: Dùng deque của hash để khỏi cần duyệt qua từng xâu con tại một xâu nhãn dán bất kì

Nhập xâu \(O(n \times k) + O(m \times k)\)

Khởi tạo \(O(i(s)) = O(Z \times n \times k \times log(MOD))\)

Truy vấn \(O(f(s)) = O(Z \times log(MOD) \times log(n))\)

Xác định \(O(v(s)) = O(\Sigma(f(s_i))) = O(q(s) \times \times Z \times log(MOD) \times log(n))\)

Tiền xử lí \(O(c(s)) = O(Z \times k)\)

Quay xâu \(O(r(s)) = O(Z \times log(MOD))\)

Xóa kí tự \(O(d(s)) = O(Z \times log(MOD))\)

Hợp hai xâu \(O(m(s)) = O(Z \times log(MOD))\)

Kiểm tra \(O(s(t)) = O(O(r(s)) + O(d(s)) + O(m(s))) + O(v(s)) \times m) = O(Z \times log(MOD) \times log(n) \times m)\)

Xuất kết quả \(O(e(s)) = O(k)\)

Kết quả \(res = O(n \times k) + O(m \times k) + O(i(s)) + O(c(s)) \times m + k \times O(s(t)) + O(e(s)) = O(Z \times log(MOD) \times k \times (n \times + Z \times log(MOD) \times log(n) \times m))\)

Lợi ích: Độ phức tạp khá hơn

Trạng thái: Quá thời gian, Sai với test kháng hash khi \(Z\) nhỏ


  • Tối ưu Polynomial-Hashing và hàng đợi hai đầu chứa hash (\(Z\) là số lượng hash)

Tối ưu: Polynomial-Hashing gồm có \(BASE\)\(MOD\) để tính \(Hash(s) = Sigma(BASE^k \times s[k]) (modulo\ MOD)\) và để tìm đoạn hash ta cần xử lí nghịch đảo modulo \((BASE^{k})^{-1} (modulo\ MOD)\). Ta tiền xử lí và lưu hết vào một mảng để giảm thời gian truy vấn phải tính toán lại

Tối ưu: Ta có thể tính hết nghịch đâỏ \((BASE ^ k)^{-1}\) trong \(O(n + log(MOD))\) (hăng số thấp đáng kể) thay vì \(O(n\ log\ MOD)\) (độ phức tạp và hằng số cao hơn) hoặc \(O(n)\) (độ phức tạp thấp nhưng hằng số rất cao)

Tối ưu: Dùng hằng số để compiler tối ưu về mặt assembly tốt đáng kể.

Tối ưu: Dùng mảng cố định độ dài thay vì vector.

Nhập xâu \(O(n \times k) + O(m \times k)\)

Khởi tạo \(O(i(s)) = O(Z \times n \times k + Sigma(log(MOD)))\)

Truy vấn \(O(f(s)) = O(1)\)

Xác định \(O(v(s)) = O(1)\)

Tiền xử lí \(O(c(s)) = O(Z \times k)\)

Quay xâu \(O(r(s)) = O(1)\)

Xóa kí tự \(O(d(s)) = O(1)\)

Hợp hai xâu \(O(m(s)) = O(1)\)

Kiểm tra \(O(s(t)) = O(O(r(s)) + O(d(s)) + O(m(s))) + O(v(s)) \times m) = O(m)\)

Xuất kết quả \(O(e(s)) = O(k)\)

Kết quả \(res = O(n \times k) + O(m \times k) + O(i(s)) + O(c(s)) \times m + k \times O(s(t)) + O(e(s)) = O(Z \times k \times (n + m) + Sigma(log(MOD)))\)

Lợi ích: Độ phức tạp khá hơn, hằng số giảm đáng kể

Trạng thái: Đúng hết, Sai với test kháng hash khi \(Z\) nhỏ


\(\color{#008b8b}{\text{Code tham khảo }}\): Tối ưu Hash, Tiền xử lí, Cấu trúc dữ liệu đặc biệt (Hash Deque), Cài đặt (Phức tạp)

\(^{^{\color{purple}{\text{Độ phức tạp : }} O(nk\ +\ mk\ +\ log(MOD))\ \color{purple}{\text{thời gian}}\ ||\ O(nk\ +\ mk)\ \color{purple}{\text{bộ nhớ}}}}\)

C++
#include <unordered_set>
#include <iostream>
#include <cstring>
#include <vector>
#include <deque>

using namespace std;

typedef long long ll;

const int MOD = 1e9 + 7;
const int BASE = 2702;
const int LIM = 2002;

/// Fast input string
char ccc;
void getString(string &s)
{
    while (ccc = getchar(), ccc != '.' && (ccc < 'a' || ccc > 'z'));

    s.assign(1, ccc);
    while (ccc = getchar(), ccc == '.' || (ccc >= 'a' && ccc <= 'z'))
        s += ccc;
}

/// (x % MOD) when (x) close to [0, MOD)
int fix(int x)
{
    while (x < 0)    x += MOD;
    while (x >= MOD) x -= MOD;
    return x;
}

/// (x ^ n) % MOD - O(log n)
int powMOD(int x, int n)
{
    int res = 1;
    for (; n > 0; n >>= 1)
    {
        if (n & 1) res = (1LL * res * x) % MOD;
        x = (1LL * x * x) % MOD;
    }

    return res;
}

/// P[k]     = (base^k)      % MOD - O(LIM)
/// INV_P[k] = (base^k)^(-1) % MOD - O(LIM + log(MOD))
int P[LIM + 1];
int INV_P[LIM + 1];
void precal()
{
    P[0] = 1;
    for (int i = 1; i <= LIM; ++i)
        P[i] = (1LL * P[i - 1] * BASE) % MOD;

    INV_P[LIM] = powMOD(P[LIM], MOD - 2);
    for (int i = LIM; i >= 1; --i)
        INV_P[i - 1] = (1LL * INV_P[i] * BASE) % MOD;
}

/// Sigma(S[i] * base^i) % MOD
int hash_value(const string &s)
{
    int h = 0;
    for (int i = 0; i < s.size(); ++i)
        h = (h + 1LL * P[i] * s[i]) % MOD;

    return h;
}

/// Merge two hashing
int hash_concat(int hash_l, int hash_r, int l_size)
{
    return (hash_l + 1LL * hash_r * P[l_size]) % MOD;
}

/// Remove last character of the hash
int hash_rollback(int hash_v, char c, int v_size)
{
    return fix((hash_v - 1LL * P[v_size - 1] * c) % MOD);
}

/// Remove first character of the hash
int hash_rollfront(int hash_v, char c)
{
    return (ll(hash_v - c) * INV_P[1]) % MOD;
}

/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

/// mxdict = max size of dictionary string
/// S[] store all valid strings
int mxdict;
unordered_set<int> dictionary;
int input_dictionary()
{
    int q;
    cin >> q;

    mxdict = 0;
    dictionary.insert(-1);
    while (q-->0)
    {
        string s;
        getString(s);
        dictionary.insert(hash_value(s));
        mxdict = max(mxdict, (int)s.size());
        // cerr << s << " -> " << hash_value(s) << endl;
    }
    // cerr << endl;
    // cerr << "===============================================\n\n";

    return 0;
}

/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

struct Circular 
{
    ///
    /// d = number of strings not in dictionary
    /// n = length of string
    /// t = deque version of string
    /// H = Hash-deque of splitted string '.' vs 'a..z'
    /// L = Size-deque of splitted string '.' vs 'a..z'
    ///
    int d;
    int n;
    deque<int> t;
    deque<int> H;
    deque<int> L;

    /// length of (s) = |s|
    int size() 
    { 
        return n; 
    }

    /// Construct Property
    void init(const string &s)
    {   
        /// Initialization
        d = 0;
        n = s.size();
        for (char c : s) t.push_back(c);

        /// Find all consecutive substring of the same type '.' or 'a..z'
        for (int l = 0, r = 0; l < n; l = r + 1)
        {
            char c = s[l];
            if (c == '.') /// All are '.'
            {
                for (r = l; r + 1 < n && s[r + 1] == '.'; ++r);
                H.push_back(-1); /// special value
                L.push_back(r - l + 1);
            }
            else /// All are latin words
            {
                for (r = l; r + 1 < n && s[r + 1] != '.'; ++r);
                H.push_back(hash_value(s.substr(l, r - l + 1)));
                L.push_back(r - l + 1);
            }
            d += !dictionary.count(H.back());
        }
    }

    /// move leftmost character to rightmost position
    void rotate_left()
    {
        /// Take first character to reroll hash
        char first = t.front();
        int hash_first = (first == '.') ? -1 : first;
        t.push_back(first);
        t.pop_front();

        /// Error before rotation
        // cerr << "\nBefore (" << d << "):\n";

        /// Insert head
        if ((H.back() == -1) ^ (H.front() == -1)) 
        { 
            /// Different type: '.' and 'a..z' -> Make new hash
            H.push_back(hash_first);
            L.push_back(1);
            d += !dictionary.count(H.back());
        }
        else
        {
            /// Same type -> Concat Hash
            if (hash_first > -1) 
            {
                d -= !dictionary.count(H.back());
                H.back() = hash_concat(H.back(), hash_first, L.back());
                d += !dictionary.count(H.back());
            }

            ++L.back();
        }

        /// Remove front
        if (L.front() == 1)
        {
            /// Pop
            d -= !dictionary.count(H.front());
            H.pop_front();
            L.pop_front();
        }
        else 
        {
            /// Reroll
            if (hash_first > -1) 
            {
                d -= !dictionary.count(H.front());
                H.front() = hash_rollfront(H.front(), first);
                d += !dictionary.count(H.front());
            }

            --L.front();
        }

        /// debug
        // cerr << "H[" << d << "] = "; for (char c : t) // cerr << c; 
        // cerr << "\n"; for (int i = 0; i < H.size(); ++i) // cerr << "# Length = " << L[i] << " | Hash = " << H[i] << endl;
    }
};

/// n = number of strings
/// k = size of any string
/// a[i] = ith string but more property
int n, k;
Circular a[LIM];
int input_labels()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        string s;
        getString(s);
        a[i].init(s);
    }

    k = a[1].size();
    return 0;
}

/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

/// cnt_valid = number of valid position
/// valid[k] = true <=> kth rotation make valid circular words
int cnt_valid;
bool valid[LIM];
bool test()
{
    /// Special cases
    if (a[1].d > 1) return false; /// One of the substring in the left  of leftmost  string is bad
    if (a[n].d > 1) return false; /// One of the substring in the right of rightmost string is bad

    /// string concatenation
    int S_cat = -1;
    int L_cat = -1;

    /// Go to each row
    for (int i = 1; i <= n + 1; ++i)
    {
        /// If there is '.' in the middle
        bool exist_a_gap = (i <= n) ? a[i].H.size() > 1 : true;

        /// Prefix string of current row
        int S_pre = (i <= n) ? a[i].H.front() : -1;
        int L_pre = (i <= n) ? a[i].L.front() : -1;

        /// Suffix string of current row
        int S_suf = (i <= n) ? a[i].H.back() : -1;
        int L_suf = (i <= n) ? a[i].L.back() : -1;

        /// Error without suffix and prefix
        int d = a[i].d;
        if (i > 1) d -= !dictionary.count(S_pre);  
        if (i < n) d -= !dictionary.count(S_suf);

        /// There is an error in the middle
        if (d > 0)
        {
            // cerr << "Not valid at (" << i << ") = " << d << " errors" << endl;
            return false;
        }

        if (S_pre != -1)
        {
            /// Nonempty string, concat with prefix in 'a..z'
            if (S_cat != -1)
            {
                S_cat = hash_concat(S_cat, S_pre, L_cat);
                L_cat += L_pre;
            }
            else /// Start new string from prefix in 'a..z' 
            {
                S_cat = S_pre;
                L_cat = L_pre;
            }
        }


        /// If its  is '.', we check whether concatenation string is dictionary string
        if (exist_a_gap && S_cat != -1)
        {
            if (!dictionary.count(S_cat))
            {
                // cerr << "Not valid at (" << i << ") = " << S_cat << ' ' << L_cat << endl;
                return false;
            }
            else 
            {
                S_cat = -1;
                L_cat = -1;
            }
        }

        /// Start new string from suffix in 'a..z'
        if (S_cat == -1 && S_suf != -1)
        {
            S_cat = S_suf;
            L_cat = L_suf;
        }   
    }

    // cerr << "Valid state <3" << endl;
    return true;
}

/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

/// Solving problem
int solve()
{
    cnt_valid = 0;
    for (int t = 0; t < k; ++t)
    {
        // cerr << "#" << t << endl;
        if (test())
        {
            ++cnt_valid;
            valid[t] = true;
        }
        // cerr << "-----------------------------------------------\n\n";

        // cerr << "Rotating:";
        /// Rotating all strings
        for (int i = 1; i <= n; ++i)
            a[i].rotate_left();

        // cerr << "===============================================\n\n";
    }

    return 0;
}

/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

/// Output result
int output()
{
    cout << cnt_valid << '\n';
    for (int t = 0; t < k; ++t)
    {
        if (valid[t])
        {
            cout << t << ' ';
        }
    }

    return 0;
}

/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

int main()
{
    precal();
    input_dictionary();
    input_labels();
    solve();
    output();
    return 0;
}

/* 
4
uuuuu
uuu
uu
u
1
uu..uu.u.uuu

-------------------------------

uu..uu.u.uuu - 2.2.1.3 
uuu..uu.u.uu - 3.2.1.2 
uuuu..uu.u.u - 4.2.1.1
uuuuu..uu.u. - 5.2.2.
.uuuuu..uu.u - .5.2.1
u.uuuuu..uu. - 1.5.2.
.u.uuuuu..uu - .1.5.2
u.u.uuuuu..u - 1.1.5.2
uu.u.uuuuu.. - 2.1.5.
.uu.u.uuuuu. - .2.1.5.
..uu.u.uuuuu - .2.1.5
u..uu.u.uuuu - 1.2.1.4

-------------------------------

S[] = uu..uu.u.uuu
# Length = 2 | Hash = 316251
# Length = 2 | Hash = -1
# Length = 2 | Hash = 316251
# Length = 1 | Hash = -1
# Length = 1 | Hash = 117
# Length = 1 | Hash = -1
# Length = 3 | Hash = 854510319

S[] = uuu..uu.u.uu
# Length = 3 | Hash = 854510319
# Length = 2 | Hash = -1
# Length = 2 | Hash = 316251
# Length = 1 | Hash = -1
# Length = 1 | Hash = 117
# Length = 1 | Hash = -1
# Length = 2 | Hash = 316251

S[] = uuuu..uu.u.u
# Length = 4 | Hash = 886865899
# Length = 2 | Hash = -1
# Length = 2 | Hash = 316251
# Length = 1 | Hash = -1
# Length = 1 | Hash = 117
# Length = 1 | Hash = -1
# Length = 1 | Hash = 117

S[] = uuuuu..uu.u.
# Length = 5 | Hash = 311642443
# Length = 2 | Hash = -1
# Length = 2 | Hash = 316251
# Length = 1 | Hash = -1
# Length = 1 | Hash = 117
# Length = 1 | Hash = -1

S[] = .uuuuu..uu.u
# Length = 1 | Hash = -1
# Length = 5 | Hash = 311642443
# Length = 2 | Hash = -1
# Length = 2 | Hash = 316251
# Length = 1 | Hash = -1
# Length = 1 | Hash = 117

S[] = u.uuuuu..uu.
# Length = 1 | Hash = 117
# Length = 1 | Hash = -1
# Length = 5 | Hash = 311642443
# Length = 2 | Hash = -1
# Length = 2 | Hash = 316251
# Length = 1 | Hash = -1

S[] = .u.uuuuu..uu
# Length = 1 | Hash = -1
# Length = 1 | Hash = 117
# Length = 1 | Hash = -1
# Length = 5 | Hash = 311642443
# Length = 2 | Hash = -1
# Length = 2 | Hash = 316251

S[] = u.u.uuuuu..u
# Length = 1 | Hash = 117
# Length = 1 | Hash = -1
# Length = 1 | Hash = 117
# Length = 1 | Hash = -1
# Length = 5 | Hash = 311642443
# Length = 2 | Hash = -1
# Length = 1 | Hash = 117

S[] = uu.u.uuuuu..
# Length = 2 | Hash = 316251
# Length = 1 | Hash = -1
# Length = 1 | Hash = 117
# Length = 1 | Hash = -1
# Length = 5 | Hash = 311642443
# Length = 2 | Hash = -1

S[] = .uu.u.uuuuu.
# Length = 1 | Hash = -1
# Length = 2 | Hash = 316251
# Length = 1 | Hash = -1
# Length = 1 | Hash = 117
# Length = 1 | Hash = -1
# Length = 5 | Hash = 311642443
# Length = 1 | Hash = -1

S[] = ..uu.u.uuuuu
# Length = 2 | Hash = -1
# Length = 2 | Hash = 316251
# Length = 1 | Hash = -1
# Length = 1 | Hash = 117
# Length = 1 | Hash = -1
# Length = 5 | Hash = 311642443

S[] = u..uu.u.uuuu
# Length = 1 | Hash = 117
# Length = 2 | Hash = -1
# Length = 2 | Hash = 316251
# Length = 1 | Hash = -1
# Length = 1 | Hash = 117
# Length = 1 | Hash = -1
# Length = 4 | Hash = 886865899
*/


Bình luận


  • 8
    SPyofgame    9:54 a.m. 30 Tháng 4, 2021

    Nghe thiên hạ đồn còn có cách sài Suffix Array và Suffix Tree cho bài này nhưng võ công thâm siêu mình không lĩnh hội được 🙁

    • 1 bình luận nữa