Pak Dengklek ingin membuat program correction suggestion ini, dengan sedikit modifikasi. Penjelasan dari algoritma ini adalah sebagai berikut. Terdapat sebuah kamus yang berisi K (1 ≤ K ≤ 5.000) buah kata yang sah, masing-masing antara 1 sampai 5.000 huruf alfabet. Setiap kali Anda menuliskan sebuah huruf, program akan mengecek potongan kata yang sah yang paling dekat dengan (potongan) kata yang Anda tulis, dan mengembalikan saran potongan kata yang sah tersebut. Bila ada beberapa kata yang sama dekatnya, tuliskan kata yang lebih dahulu muncul pada masukan.
Kedekatan dua buah potongan kata dengan panjang sama adalah jumlah kedekatan antar dua huruf yang terletak di posisi yang sama. Kedekatan antar dua huruf ditentukan oleh jarak minimal keduanya dalam urutan alphabet 'a'-'z' (sirkular, sehingga kedekatan 'a' dan 'z' adalah 1). Misalnya, kedekatan antara "dara" dan "carb" adalah 1+0+0+1 = 2.
Bantulah Pak Dengklek membuat program correction suggestion yang menyebalkan ini.
Format Masukan
Baris pertama berisi sebuah bilangan bulat K. K baris berikutnya berisi kata-kata sah yang ada dalam kamus tersebut. Baris berikutnya berisi sebuah kata (query) antara 1 sampai 5.000 karakter. Dijamin selalu ada kata dalam kamus dengan panjang lebih dari atau sama dengan query.Format Keluaran
Baris-baris sebanyak panjang kata query. Baris ke-i berisi saran yang akan diberikan program saat pengguna sudah mengetik i huruf pertama dari query.Contoh Masukan
5 character charade cats cabaret blade chabter
Contoh Keluaran
c ch cha blad cabar cabare cabaret
So, the answer is :
0 komentar:
Posting Komentar