تجزئة سلسلة هي تمثيل لسلسلة باعتبارها عددًا ما ، فريدًا (سنفترض أن احتمال حدوث تضارب ضئيل) لكل سلسلة. يسمح لك هذا بتخزين أي بيانات مهمة (مثل كلمات المرور) في قاعدة البيانات ليس كسلاسل ، ولكن كأرقام. يتيح لك ذلك حماية كلمات المرور إذا تمكن المهاجم من الوصول إلى قاعدة بيانات كلمات المرور ، لأنه لن يحصل على كلمات المرور بنفسه ، ولكن فقط تمثيلها العددي ، ويكاد يكون من المستحيل الحصول على سلسلة من خلال التجزئة الخاصة بها (خاصةً دون معرفة خوارزمية التجزئة ). & nbsp؛
غالبًا ما تستخدم التجزئة متعددة الحدود في برمجة مشاكل المنافسة.
من أفضل الطرق لتحديد دالة التجزئة للسلسلة S كما يلي:
h (S) & nbsp؛ = & نبسب ؛ S [0] نبسب ؛ + نبسب ؛ S [1] * P & nbsp؛ + نبسب ؛ S [2] * P ^ 2 & nbsp؛ + نبسب ؛ S [3] * P ^ 3 & nbsp؛ + نبسب ؛ ... نبسب ؛ + نبسب ؛ S [N] * P ^ N
Problem
كان المبرمج فاسيا سيئ الحظ - فبدلاً من إجازة ، تم إرساله في رحلة عمل لحضور مؤتمر علمي. قال الرئيس: "نحن بحاجة إلى زيادة مستوى المعرفة ، يعقد مؤتمر مهم حول التشفير في فرنسا - وهناك قاموا بتشفيرها مرة أخرى في زمن ريشيليو وعملوا على فك شفرات الآخرين في زمن فيتا".
سرعان ما اكتشف فاسيا أنه شاهد بالفعل جميع لوحات اللوفر في مكان ما ، وأصبح مشهد برج إيفل مملًا له حتى قبل أن يمسحه الفأر عن السجادة ، ونحن نصنع مثل هذه الأهرامات الزجاجية لجميع أنواع الأكشاك و مطاعم مشكوك فيها. باختصار ، لم يكن هناك شيء تراه في باريس ، ولم يكن هناك مكان للصيد ، لذلك كان على فاسيا حضور التقارير في المؤتمر.
أحد المتحدثين ، الذي حاول مرة أخرى كشف أصفار بيكون ، طرح فرضية مفادها أنه يمكن العثور على مفتاح أسرار بيكون من خلال تحليل جميع السلاسل الفرعية المحتملة لأعمال بيكون. "لكن هناك الكثير منهم!" فوجئ فاسيا بصوت عالٍ. "لا ، ليس كثيرا!" - صاح المتكلم ، - "احسب ، وسترى بنفسك!"
في نفس المساء ، وجد Vasya الأعمال الكاملة لـ Bacon على الإنترنت. كتب برنامجًا حول النصوص إلى سطر طويل واحد ، وأزال جميع المسافات وعلامات الترقيم من النصوص. والآن Vasya في حيرة شديدة - كيف نحسب عدد السلاسل الفرعية المختلفة لهذه السلسلة؟ & nbsp ؛
إدخال
يحتوي الإدخال على سلسلة غير فارغة تلقاها Vasya. تتكون السلسلة من أحرف لاتينية صغيرة فقط. طوله لا يتجاوز 2000 حرف. & nbsp؛
الإخراج
اطبع عدد السلاسل الفرعية المختلفة لهذه السلسلة.
نبسب ؛
أمثلة
| # |
إدخال |
الإخراج |
<الجسم>
| 1 |
آبا |
8 |