في نظرية الترميز ، غالبًا ما تُستخدم الرموز غير المسبوقة كمجموعات من الكلمات ، وليس أي منها بادئة. يقال إن الكلمة & alpha؛ تسبق الكلمة & beta؛ إذا تم الحصول على & alpha؛ من & beta؛ بالحذف صفر أو أكثر من الأحرف في النهاية. على سبيل المثال ، الكلمات a و ab و aba هي بادئات لكلمة aba . على سبيل المثال ، مجموعة الكلمات aba و aa و bac هي رمز غير مسبوق ، بينما مجموعة abac ، aba ، ba غير موجود لأن كلمة aba هي بادئة لكلمة abac .
& nbsp؛ يعمل البروفيسور ديكفيرس في مختبر أبحاث المعلومات عديمة الفائدة ويدرس اختراعه الجديد للرموز شبه البادئة. تسمى مجموعة الكلمات رمز المستوى k الخالي من البادئات تقريبًا إذا كان أكبر بادئة مشتركة لأي كلمتين من المجموعة لا يتجاوز طولها k . على سبيل المثال ، المجموعة abac ، abc ، ba هي رمز المستوى 2 غير مسبوق تقريبًا والمجموعة abac ، abab ، ba غير موجودة لأن أطول بادئة مشتركة لـ abac و abab هي 3.
& nbsp؛ المهمة التالية التي حددها البروفيسور Decifro لمساعديه في المختبر هي كما يلي: نظرًا لمجموعة من الكلمات ورقم k ، يلزم الاختيار من بين المعطى الكلمات الحد الأقصى للمجموعة ، وهو رمز مستوى خالٍ من البادئات تقريبًا k . بصفتك مساعد مختبر مبتدئ ، تم تكليفك بكتابة البرنامج المناسب.
يحتوي السطر الأول من ملف الإدخال على عددين صحيحين:
n و
k عدد الكلمات في المجموعة المحددة ومستوى الشفرة غير المبرمجة تقريبًا التي سيتم بناؤها (
\ (1 & lt؛ = n & lt؛ = 100000 \) ،
\ (0 & lt؛ = k & lt؛ = 200 \) ). تحتوي سطور n التالية على كلمة واحدة لكل سطر. تتكون الكلمات من أحرف صغيرة من الأبجدية اللاتينية. يتراوح طول كل كلمة من 1 إلى 200 حرف. لا يتجاوز الطول الإجمالي لجميع الكلمات \ (10 ^ 6 \) . كل الكلمات مختلفة.
& nbsp؛
الإخراج
إخراج رقم واحد
m - الحد الأقصى لعدد الكلمات التي يمكن اختيارها من المجموعة المحددة بحيث تشكل رمز مستوى
k غير مسبوق تقريبًا. & nbsp؛
نبسب ؛
أمثلة
| # |
إدخال |
الإخراج |
<الجسم>
| 1 |
6 2
|
3 |