/image%2F1089143%2F20150731%2Fob_9d97aa_1.jpg)
Top posts
-
Spoj SEC
Bessie định dẫn đàn bò đi trốn. Để đảm bảo bí mật, đàn bò liên lạc với nhau bằng cách tin nhắn nhị phân. Từng là một nhân viên phản gián thông minh, John đã thu được M (1 <= M <= 50,000) tin nhắn mật, tuy nhiên với tin nhắn i John chỉ thu được b_i (1...
-
UVA 12526 - Cellphone Typing
Một nhóm nghiên cứu đang tìm cách phát triển 1 phần mềm giúp gõ bàn phím nhanh hơn bằng cách phát triển 1 tập từ điển gồm n xâu, giả sử khi gõ 1 xâu P, ta đã gõ đến vị trí i, c1c2...ci, phần mềm sẽ kiểm tra xem nếu tồn tại 1 kí tự c sao cho tất cả các...
-
[Latin America 2011] Diccionário Portuñol
Cho 2 tập xâu S, P (|S|, |P| <=1000, mỗi xâu có độ dài <=1000, tổng độ dài mỗi tập <=10^5) Đếm số xâu khác nhau tạo được bằng cách nối 1 prefix khác rỗng của S với 1 suffix khác rỗng của P. Sample Input 3 3 mais grande mundo mas grande mundo 1 5 a aaaaa...
-
UVA 12506 Shortest Names
Trong 1 ngôi làng, mọi người đều có tên rất dài. Để thuận tiện họ gọi nhau = prefix của tên. Một prefix của tên 1 người có thể được dùng để gọi người đó nếu nó ko fai là prefix của tên 1 người khác. Cho tên của n người trong làng (n<=1000, tổng độ dài...
-
Spoj Chain2
Chuỗi từ có độ dài n là một dãy các từ w1, w2, ..., wn sao cho với mọi 1 ≤ i < n, từ wi là tiền tố của từ wi+1. Nhắc lại từ u có độ dài k là tiền tố của từ v có độ dài l nếu l > k và các ký tự đầu tiên của v trùng với từ u. Cho tập hợp các từ S={s1, s2,...
-
[Manacher] Spoj Paliny
Tìm substring dài nhất là palindrome của 1 xâu S |S|<=50000 Manacher: Đầu tiên biến đổi xâu S bằng cách thêm xen giữa các kí tự của S kí tự #, thêm vào đầu S kí tự ^, cuối S kí tự $ Ví dụ S=abba => S=^#a#b#b#a#$ Như vậy mọi Palin Substring (PS) bây giờ...
-
[Hashing 2 dimensions] UVA 11019 Matrix Matcher
Given an N * M matrix, your task is to find the number of occurences of an X * Y pattern (N,M<=1000, X,Y<=100) Algorithm: Hashings trên ma trận 2 chiều: ull hash() { ull res=0; FOR(i,0,x-1) { ull u=0; FOR(j,0,y-1) u=u*base1+b[i][j]; res=res*base2+u; }...
-
CF126B Password
Cho xâu S |S|<=1000.000. Tìm substring P dài nhất của S sao cho P vừa là prefix vừa là suffix vừa xuất hiện ở giữa S (không trùng prefix, suffix) Sample test(s) input fixprefixsuffix output fix input abcdabc output Just a legend Dùng Z-algorithm xấy dựng...
-
CF79C Beaver
Cho n xâu b1,b2,..,bn được xem là boring và xâu S. Tìm substring dài nhất của S ko chứa n xâu boring như là substring (n<=10, |S|<=10^5) Sample test(s) input Go_straight_along_this_street 5 str long tree biginteger ellipse output 12 4 input IhaveNoIdea...
-
CF 432D Prefixes and Suffixes
Cho xâu S, nhiệm vụ là với mỗi xâu con vừa là prefix vừa là suffix in ra số lần nó xuất hiện trong S. |S|<=10^5 Algorithm: Để làm được bài này cần hiểu sâu sắc ý nghĩa của prefix function trong phần khởi tạo của KMP F[0] = F[1] = 0; for(int i = 2;i<=n;i++){...
-
[Manacher] Codechef TACHEMIS
http://www.codechef.com/problems/TACHEMIS Algorithm: Áp dụng manacher cho n compressed string Do nếu các các compressed string ghép lại đk thành 1 PS thì độ dài của PS đó chắc chắn lẻ nên ta ko cần bước thêm các "#" như Manacher nguyên bản int C = 1,...
-
[Jakarta 2013] Pasti Pas!
UMột xâu có thể được viết thành dạng palindrom nếu ta thay 1 hoặc 1 số substring của nó = 1 biểu tượng khá. Ví dụ Let S = ‘ABCADDABCA’. There are several derivations of S, e.g.: • Let α = ‘ABCA’, β = ‘DD’, then S′ = ‘αβα’ which has a length of 3. • Let...