Hướng dẫn cho Eticket (DHBB 2021 T.Thử)
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:
\(\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\) và \(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ớ}}}}\)
#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
orz
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 🙁