SPOJ.COM - Thuật toán bài NABILHACKER - Hack the Password

10/10/2018 13 minutes read

Đề bài

Rất nhiều người hỏi mình về vấn đề áp dụng lập trình ở cuộc thi vào các project trong đời sống thực chất là gì? Điều này có vẻ không mấy thú vị. Cái mà mình thấy thực sự thú vị đó là, vào một ngày nọ, một người bạn - là hacker đã đến gặp mình. Anh ta yêu cầu mình giải quyết một bài toán về hacking của anh ấy.

Khi bạn muốn lấy cắp mật khẩu của ai đó, bạn có thể cài đặt chương trình KeyLogger trên máy tính của người đó. KeyLogger sẽ đưa cho bạn một string đóng vai trò là password. Nhưng có một vấn đề, đó là nó sẽ đưa cho bạn tất cả mọi thứ mà nạn nhân đã gõ, bao gồm cả phím dịch trái, dịch phải, backspace.

Giả sử nạn nhân gõ password "generio312", nhưng dựa trên kịch bản là:

Anh ta gõ "generio1"
Sau đó, anh ta nhấn nút dịch trái, và nhấn 3. Lúc này password sẽ là "generio31"
Rồi anh ta nhấn dịch phải, và nhấn 2. Lúc này password là "generio312"
Cuối cùng anh ta nhấn "ghj" và nhấn backspace 3 lần để xoá 3 kí tự này đi. Vì vậy, password cuối cùng sẽ là "generio312".

Tuy nhiên, như mình đã nói, KeyLogger sẽ đưa cho bạn tất cả những gì mà anh ta gõ. Do đó, bạn sẽ nhận được string là "generio1<3>2ghj---". Trong đó, < là dịch trái, > là dịch phải và - là backspace.

Đầu vào

Tại vị trí đầu tiên của input là số T, số lượng của testcase. Sau đó, có T string s, với độ dài 1 <= |s| <= 10^6. Mỗi string sẽ bao gồm chữ cái in hoa, chữ cái in thường, dấu <, dấu >, dấu - và các số [0, 9]

Đầu ra

Đầu ra sẽ là một string ở mỗi dòng - tương ứng với password.

Ví dụ

Input:

2
<<BP<A>>Cd-
ThisIsS3Cr3t

Output:

BAPC
ThisIsS3Cr3t

Phân tích bài toán

Đầu tiên, khi đọc bài toán này, mình nghĩ ngay đến việc sử dụng List. Nhưng không phải là Singly Linked List mà mình cần có một con trỏ để xác định vị trí hiện tại - nơi mà mình sẽ thực hiện các hành động (dịch trái, dịch phải, xóa, chèn thêm 1 kí tự).

Tuy nhiên, cách này sẽ bị lâu ở chỗ là mình cần phải tạo thêm node, xóa node, thay đổi liên kết của node. Vì vậy, mình nghĩ đến cách thứ 2 đó là sử dụng 2 stack.

Vì mình thấy cách triển khai của bài này rất giống với cách triển khai thuật toán Undo-Redo.

Tư tưởng của thuật toán này là:

Giả sử mình có 2 stack là: stMain và stBuffer
Khi duyệt string input:
- Nếu là kí tự dịch trái (<): pop ở stMain rồi push vào stBuffer
- Nếu là kí tự dịch phải (>): pop ở stBuffer rồi push vào stMain
- Nếu là kí tự backspace (-): pop ở stMain
- Nếu là kí tự còn lại: push vào stMain
Sau khi duyệt hết string input: mình chỉ cần ghép stMain và stBuffer vào là được.

Kể ra có cái hình vẽ minh họa thì bạn sẽ dễ hiểu hơn mà mình lười vẽ quá, nên thôi vậy. Bạn chịu khó xem cách mình triển khai code ở phía dưới.

Chỗ nào chưa hiểu thì bạn có thể hỏi mình bằng cách đặt bình luận phía dưới, mình sẽ cố gắng giải đáp.

Lời giải

(Các bạn nên tự mình nghĩ ra thuật toán của bài toán trước khi tham khảo code của mình nhé. Hãy phát huy tối đa khả năng sáng tạo của bản thân. Hơn nữa code mình viết ra cũng chưa thật sự tối ưu. Nên rất mong nhận được sự chia sẻ của các bạn.)

Cách 1: Sử dụng List (0.13s / 12M)

      
        #include <iostream>
      
        using namespace std;
      
        const int MAX_N = 1000001;
      
        char input[MAX_N], output[MAX_N];
      
        // Node 
      
        struct Node {
      
        	char data;
      
        	Node *next;
      
        	Node *prev;
      
        };
      
        Node* initNode(char data = '\0') {
      
        	Node* node = new Node;
      
        	node->data = data;
      
        	node->next = NULL;
      
        	node->prev = NULL;
      
        	return node;
      
        }
      
        // List
      
        struct List {
      
        	Node* root;
      
        	Node* current;
      
        };
      
        List* initList() {
      
        	List* list = new List;
      
        	list->root = initNode();
      
        	list->current = list->root;
      
        	return list;
      
        }
      
        void deleteList(List *list) {
      
        	Node *root = list->root;
      
        	while(root->next != NULL) {
      
        		Node* tmp = root->next;
      
        		root->next = root->next->next;
      
        		delete tmp;
      
        	}
      
        	delete root;
      
        	delete list;
      
        }
      
        void moveLeft(List *list) {
      
        	Node *p = list->current->prev;
      
        	if (p) list->current = p; 
      
        }
      
        void moveRight(List *list) {
      
        	Node *p = list->current->next;
      
        	if (p) list->current = p; 
      
        }
      
        void backspace(List *list) {
      
        	if (list->current->prev) {
      
        		Node *curr = list->current;
      
        		Node *prev = curr->prev;
      
        		Node *next = curr->next;
      
        		if (prev) prev->next = next;
      
        		if (next) next->prev = prev;
      
        		list->current = prev;
      
        		delete curr;
      
        	}
      
        }
      
        void addItem(List *list, char data) {
      
        	Node* node = initNode(data);
      
        	Node* next = list->current->next;
      
        	list->current->next = node;
      
        	node->prev = list->current;
      
        	node->next = next;
      
        	if (next) next->prev = node;
      
        	list->current = node;
      
        }
      
        void build(List *list, char *output) {
      
        	Node *p = list->root;
      
        	int index = 0;
      
        	while(p->next != NULL) {
      
        		output[index] = p->next->data;
      
        		p = p->next;
      
        		index++;
      
        	}
      
        	output[index] = '\0';
      
        }
      
        void getPassword(List *list, char* output, char* input) {
      
        	int index = 0;
      
        	char current = '\0';
      
        	while(true) {
      
        		current = input[index];
      
        		if (current == '\0') break;
      
        		if (current == '<') {
      
        			moveLeft(list);
      
        		} else if (current == '>') {
      
        			moveRight(list);
      
        		} else if (current == '-') {
      
        			backspace(list);
      
        		} else {
      
        			addItem(list, current);
      
        		}
      
        		index++;
      
        	}
      
        	build(list, output);
      
        }
      
        int main() {
      
        	ios::sync_with_stdio(false);
      
        	//freopen("input.txt", "r", stdin);
      
        	int T;
      
        	cin >> T;
      
        	for(int tc = 0; tc < T; tc++) {
      
        		List *list = initList();
      
        		cin >> input;
      
        		getPassword(list, output, input);
      
        		cout << output << endl;
      
        		deleteList(list);
      
        	}
      
        	return 0;
      
        }

view raw NABILHACKER-list.cpp hosted with ❤ by GitHub

Cách 2: Sử dụng Stack (0.02s / 4.7M)

      
        // Using stack
      
        #include <iostream>
      
        using namespace std;
      
        const int MAX_N = 1000001;
      
        char input[MAX_N], output[MAX_N];
      
        // Stack
      
        struct Stack {
      
        	char* data;
      
        	int length;
      
        };
      
        Stack* initStack(int maxLength) {
      
        	Stack* st = new Stack;
      
        	st->data = new char[maxLength];
      
        	st->length = 0;
      
        	st->data[st->length] = '\0';
      
        	return st;
      
        }
      
        void destroyStack(Stack *st) {
      
        	delete[] st->data;
      
        	delete st;
      
        }
      
        int getLength(Stack *st) {
      
        	return st->length;
      
        }
      
        bool isEmpty(Stack *st) {
      
        	return st->length == 0;
      
        }
      
        bool isFull(Stack *st) {
      
        	return st->length == MAX_N;
      
        }
      
        void push(Stack *st, char data) {
      
        	if (!isFull(st) && data != '\0') {
      
        		st->data[st->length] = data;
      
        		st->length++;
      
        		st->data[st->length] = '\0';
      
        	}
      
        }
      
        char pop(Stack *st) {
      
        	if (!isEmpty(st)) {
      
        		char data = st->data[st->length - 1];
      
        		st->length--;
      
        		st->data[st->length] = '\0';
      
        		return data;
      
        	}
      
        	return '\0';
      
        }
      
        // End of Stack
      
        int getLength(char *input) {
      
          int index = 0;
      
        	while(input[index] != '\0') index++;
      
        	return index;
      
        }
      
        void concat(char *output, char *input1, char *input2) {
      
        	int index1 = 0;
      
        	while(input1[index1] != '\0') {
      
        		output[index1++] = input1[index1]; 
      
        	}
      
        	int index2 = getLength(input2) - 1;
      
        	int cnt = 0;
      
        	while(index2 >= 0) {
      
        		output[index1 + cnt++] = input2[index2--]; 
      
        	}
      
        	output[index1 + cnt] = '\0';
      
        }
      
        void getPassword(char *output, char* input) {
      
        	Stack* stMain = initStack(MAX_N);
      
        	Stack* stBuffer = initStack(MAX_N);
      
        	int index = 0;
      
        	char current = '\0';
      
        	while(true) {
      
        		current = input[index];
      
        		if (current == '\0') break;
      
        		if (current == '<') {
      
        			push(stBuffer, pop(stMain));
      
        		} else if (current == '>') {
      
        			push(stMain, pop(stBuffer));
      
        		} else if (current == '-') {
      
        			pop(stMain);
      
        		} else {
      
        			push(stMain, current);
      
        		}
      
        		index++;
      
        	}
      
        	concat(output, stMain->data, stBuffer->data);
      
        	destroyStack(stMain);
      
        	destroyStack(stBuffer);
      
        }
      
        int main() {
      
        	ios::sync_with_stdio(false);
      
        	//freopen("input.txt", "r", stdin);
      
        	int T;
      
        	cin >> T;
      
        	for(int tc = 0; tc < T; tc++) {
      
        		cin >> input;
      
        		getPassword(output, input);
      
        		cout << output << endl;
      
        	}
      
        	return 0;
      
        }

view raw NABILHACKER-stack.cpp hosted with ❤ by GitHub

Thân ái, Phạm Văn Lâm

spoj, Tham lam - Greedy

phạm văn lâm, spoj.com, thuật toán, thuật toán spoj.com, tham lam greedy, stack

Quay lại

	#include <iostream>
	using namespace std;

	const int MAX_N = 1000001;
	char input[MAX_N], output[MAX_N];

	// Node
	struct Node {
	char data;
	Node *next;
	Node *prev;
	};

	Node* initNode(char data = '\0') {
	Node* node = new Node;
	node->data = data;
	node->next = NULL;
	node->prev = NULL;
	return node;
	}

	// List
	struct List {
	Node* root;
	Node* current;
	};

	List* initList() {
	List* list = new List;
	list->root = initNode();
	list->current = list->root;
	return list;
	}

	void deleteList(List *list) {
	Node *root = list->root;

	while(root->next != NULL) {
	Node* tmp = root->next;
	root->next = root->next->next;
	delete tmp;
	}

	delete root;
	delete list;
	}

	void moveLeft(List *list) {
	Node *p = list->current->prev;
	if (p) list->current = p;
	}

	void moveRight(List *list) {
	Node *p = list->current->next;
	if (p) list->current = p;
	}

	void backspace(List *list) {
	if (list->current->prev) {
	Node *curr = list->current;
	Node *prev = curr->prev;
	Node *next = curr->next;

	if (prev) prev->next = next;
	if (next) next->prev = prev;

	list->current = prev;
	delete curr;
	}
	}

	void addItem(List *list, char data) {
	Node* node = initNode(data);
	Node* next = list->current->next;
	list->current->next = node;
	node->prev = list->current;
	node->next = next;
	if (next) next->prev = node;
	list->current = node;
	}

	void build(List list, char output) {
	Node *p = list->root;
	int index = 0;

	while(p->next != NULL) {
	output[index] = p->next->data;
	p = p->next;
	index++;
	}

	output[index] = '\0';
	}

	void getPassword(List list, char output, char* input) {
	int index = 0;
	char current = '\0';

	while(true) {
	current = input[index];
	if (current == '\0') break;

	if (current == '<') {
	moveLeft(list);
	} else if (current == '>') {
	moveRight(list);
	} else if (current == '-') {
	backspace(list);
	} else {
	addItem(list, current);
	}

	index++;
	}

	build(list, output);
	}

	int main() {
	ios::sync_with_stdio(false);
	//freopen("input.txt", "r", stdin);

	int T;
	cin >> T;

	for(int tc = 0; tc < T; tc++) {
	List *list = initList();
	cin >> input;
	getPassword(list, output, input);
	cout << output << endl;
	deleteList(list);
	}

	return 0;
	}

	// Using stack
	#include <iostream>
	using namespace std;

	const int MAX_N = 1000001;
	char input[MAX_N], output[MAX_N];

	// Stack
	struct Stack {
	char* data;
	int length;
	};

	Stack* initStack(int maxLength) {
	Stack* st = new Stack;
	st->data = new char[maxLength];
	st->length = 0;
	st->data[st->length] = '\0';
	return st;
	}

	void destroyStack(Stack *st) {
	delete[] st->data;
	delete st;
	}

	int getLength(Stack *st) {
	return st->length;
	}

	bool isEmpty(Stack *st) {
	return st->length == 0;
	}

	bool isFull(Stack *st) {
	return st->length == MAX_N;
	}

	void push(Stack *st, char data) {
	if (!isFull(st) && data != '\0') {
	st->data[st->length] = data;
	st->length++;
	st->data[st->length] = '\0';
	}
	}

	char pop(Stack *st) {
	if (!isEmpty(st)) {
	char data = st->data[st->length - 1];
	st->length--;
	st->data[st->length] = '\0';
	return data;
	}

	return '\0';
	}
	// End of Stack

	int getLength(char *input) {
	int index = 0;
	while(input[index] != '\0') index++;
	return index;
	}

	void concat(char output, char input1, char *input2) {
	int index1 = 0;
	while(input1[index1] != '\0') {
	output[index1++] = input1[index1];
	}

	int index2 = getLength(input2) - 1;
	int cnt = 0;
	while(index2 >= 0) {
	output[index1 + cnt++] = input2[index2--];
	}

	output[index1 + cnt] = '\0';
	}

	void getPassword(char output, char input) {
	Stack* stMain = initStack(MAX_N);
	Stack* stBuffer = initStack(MAX_N);

	int index = 0;
	char current = '\0';

	while(true) {
	current = input[index];
	if (current == '\0') break;

	if (current == '<') {
	push(stBuffer, pop(stMain));
	} else if (current == '>') {
	push(stMain, pop(stBuffer));
	} else if (current == '-') {
	pop(stMain);
	} else {
	push(stMain, current);
	}

	index++;
	}

	concat(output, stMain->data, stBuffer->data);
	destroyStack(stMain);
	destroyStack(stBuffer);
	}

	int main() {
	ios::sync_with_stdio(false);
	//freopen("input.txt", "r", stdin);

	int T;
	cin >> T;

	for(int tc = 0; tc < T; tc++) {
	cin >> input;
	getPassword(output, input);
	cout << output << endl;
	}

	return 0;
	}