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

Posted on October 10th, 2018

Đề 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à:

  1. Anh ta gõ "generio1"
  2. Sau đó, anh ta nhấn nút dịch trái, và nhấn 3. Lúc này password sẽ là "generio31"
  3. Rồi anh ta nhấn dịch phải, và nhấn 2. Lúc này password là "generio312"
  4. 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

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 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;
}

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;
}

★ Nếu bạn thấy bài viết này hay thì hãy theo dõi mình trên Facebook để nhận được thông báo khi có bài viết mới nhất nhé:

Xin chào và hẹn gặp lại, thân ái!