Hướng dẫn giải của TRIETORTURE
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Ta tạo một mảng các câu lệnh. Mỗi câu lệnh được biểu diễn dưới dạng tuple\<string, int, int>. Nếu câu lệnh là CONCATENATE thì trường thứ nhất là xâu rỗng, trường thứ 2 và thứ 3 là hai xâu được ghép. Nếu câu lệnh là DECLARE thì trường thì nhất là nội dung xâu, còn hai trường còn lại có thể để bất kì.
Tạo một trie gồm tất cả các pattern. Đặt current là con trỏ tới gốc của trie. Ta sẽ thực hiện một thuật toán đệ quy trên xâu cần kiểm tra. Sau đây là mã giả:
int node_pointer = 0;
bool found = false;
bool dfs(int string_index) {
if (get<0>(strings[string_index]) == "") {
int left = get<1>(strings[string_index]);
int right = get<2>(strings[string_index]);
if (dfs(left)) return true;
if (dfs(right)) return true;
} else {
auto &string = get<0>(strings[string_index]);
for (char c: string) {
node_pointer = trie[node_pointer].children[c];
if (node_pointer == -1) return true;
if (trie[node_pointer].is_end_of_some_string) {
found = true;
return true;
}
}
}
return false;
}
Biến found sẽ đổi thành true nếu xâu cần kiểm tra có tiền tố là một
trong các pattern đã cho.
Ngoài dùng trie, chúng ta cũng có thể dùng hash, KMP, Z algorithm để giải.
Bình luận