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 từ trong từ điểm có prefix là c1c2...ci thì sẽ có prefix c1c2..cic thì sẽ tự động điền kí tự c cho người dùng. Cho 1 tập từ điển xâu A (tổng độ dài <= 800000). Đếm số lượng kí tự trung bình để viết hết tập xâu A. Lưu ý phần mềm sẽ ko đoán kí tự đầu tiên.

Ví dụ

4

hello
hell
heaven
goodbye

Để viết chữ hello, người dùng gõ h, hệ thống tự điền e vì 3 từ hello, hell, heaven có prefix là h đều có prefix là he, tiếp đó người dùng fai tự nhập kí tự l (phần mềm ko thể đoán do hell và heaven), phần mềm tự động điền l , tiep theo người dùng cần tự bấm o do phần mềm ko phân biệt được tiếp theo nên điền o hay dừng (vì trong từ điển có từ hell)

Vậy để viết chữ hello cần bấm 3 phát.

Tương tự như vậy hell => bấm 2 lần , heaven => bấm 2 lần, goodbye => 1 lần

Giá trị cần tìm là (2+2+3+1)/4=2

Algorithm:

Xây dựng cây trie của tập xâu. Nhận xét 1 nút nếu có >=2 con hoặc là kết thúc của 1 từ thì nút con của nó cần phải bị nhập thủ công.

Vậy với mỗi nút có thêm các tham số:

sl: số từ đi qua nút đó

stop: true/false xem nút đó có fai nút dừng ko

void add(string s)
{
Trie* now=root;
FOR(i,0,s.length()-1)
{
int ch=s[i]-'a';
if (now->next[ch]==NULL)
{
now->next[ch]=new Trie();
}
now=now->next[ch];
now->sl++;
}
now->stop=true;
}




void dfs(Trie* now,int dep)
{
int dem=0;
FOR(i,0,25)
if (now->next[i]!=NULL)
{
dem++;
dfs(now->next[i],dep+1);
}

if (dem>1 || now->stop)
if (dep>0)
res=res+now->sl;

}