Hack Hashing

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
NguyenHuuNhatQuang
Dạng bài
Điểm: 200 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Thuật toán Rabin-Karp là một thuật toán rất phổ biến trong lập trình thi đấu vì sự đa năng của nó. Thuật toán này biến một xâu \(s\) thành một số nguyên ký hiệu là \(hash(s)\), sao cho mỗi xâu \(s\) chỉ có một \(hash(s)\), nhưng có thể có nhiều xâu \(s\) có thể thu được từ một số nguyên \(hash(s)\).

Cụ thể hơn, thuật toán hoạt động như sau:

  • Chọn một cơ số \(b \ge 255\) và một modulo \(m\).
  • Đặt \(hash("") = 0\).
  • Với một xâu \(a\) và một ký tự \(c\), \(hash(a + c) = (hash(a) * b + v(c))\ \%\ m\), với \(v(c)\) là thứ tự của ký tự \(c\) trong bảng mã ASCII.

Ta có thể thấy, với hai xâu \(s\) và \(t\):

  • Nếu \(hash(s)\neq hash(t)\) thì \(s\neq t\).
  • Nếu \(hash(s) = hash(t)\) thì nhiều khả năng \(s = t\).

Bạn được cho trước hai số nguyên \(b\) và \(m\), bạn phải tìm hai xâu \(s\) và \(t\) gồm các chữ cái in thường trong bảng chữ cái tiếng Anh sao cho \(hash(s)=hash(t)\) nhưng \(s\neq t\). Nếu có nhiều cặp xâu như vậy, in ra một cặp bất kỳ.

Lưu ý: judge_output chỉ để cho vui, không có giá trị gì đâu :D, nên đừng có print cái đấy ra nhé.

Constrants

  • \(b, m \le 10^6\).

Scoring

Với \(|s|\) và \(|t|\) lần lượt là độ dài hai xâu \(s\) và \(t\), bạn sẽ nhận được:

  • Subtask \(1\) (\(25\%\) số điểm): \(|s|, |t| \le 10^6\).
  • Subtask \(2\) (\(10\%\) số điểm): \(|s|, |t| \le 10^5\).
  • Subtask \(3\) (\(10\%\) số điểm): \(|s|, |t| \le 10^4\).
  • Subtask \(4\) (\(15\%\) số điểm): \(|s|, |t| \le 10^3\).
  • Subtask \(5\) (\(10\%\) số điểm): \(|s|, |t| \le 100\).
  • Subtask \(6\) (\(15\%\) số điểm): \(|s|, |t| \le 10\).
  • Subtask \(7\) (\(15\%\) số điểm): \(|s|, |t| \le 5\).

Example

Test 1

Input 
255 773
Output 
a
ab
Note
  • Ta có \(hash("a") = hash("")*255+97 = 97\).
  • Ta có \(hash("ab") = (hash("a")*255+98)\ \% \ 773=97\).

Bình luận