188 - Perfect Hash
پنجشنبه, ۱ تیر ۱۳۹۱، ۰۸:۲۶ ب.ظ
لینک سوال :
مفهوم سوال :
سوال میگه یه hash function داریم که میاد یه کلمه می گیره و بوسیله یه عدد ثابت C به یه عدد صحیح می بره .
سوال میگه برای یه جمله دلخواه که میده ، کوچکترین مقدار C رو بدست بیارید که بعد از hash ، هیچ دو تا کلمه ای به یه عدد hash نشده باشن .
حل :
حل این سوال تو حالت کلی کار آسونی نیست ولی چیزی که این سوال رو آسون کرده اینه که تو statement یه الگوریتم ارائه شده که با اون مقدار C حساب میشه .
برای حل کافیه شما الگوریتم مطرح شده رو پیاده سازی کنید .
یعنی به ازای هر مقدار C چک کنید کف conflict هست یا نه ، اگه بود به راحتی مقدار بعدی C بدست میاد.
حواستون باشه که بعد از بار تغییر دادن C باید کل کلمات با مقدار جدید چک بشن .
