Problem

2 /2


HASH

Theory Click to read/hide

هش کردن یک رشته نمایشی از یک رشته به عنوان یک عدد، منحصر به فرد (فرض می کنیم که احتمال برخورد ناچیز است) برای هر رشته است. این به شما اجازه می دهد تا هر داده مهم (مانند رمزهای عبور) را در پایگاه داده نه به عنوان رشته، بلکه به عنوان اعداد ذخیره کنید. این به شما امکان می دهد تا در صورت دسترسی مهاجم به پایگاه داده رمز عبور، از رمزهای عبور محافظت کنید، زیرا او رمزهای عبور خود را دریافت نمی کند، بلکه فقط نمایش عددی آنها را دریافت می کند و تقریباً غیرممکن است که یک رشته را با هش آن به دست آورید (به ویژه بدون دانستن الگوریتم هش). ). 
هش‌های چندجمله‌ای اغلب در مسائل مسابقه برنامه‌نویسی استفاده می‌شوند.
یکی از بهترین راه ها برای تعیین تابع هش رشته S به شرح زیر است:
h(S)  =  S[0]  +  S[1] * P  +  S[2] * P^2  +  S[3] * P^3  +  ...  +  S[N] * P^N

Problem

برنامه نویس واسیا بدشانس بود - به جای تعطیلات، او را به یک سفر کاری به یک کنفرانس علمی فرستادند. رئیس گفت: "ما باید سطح دانش را افزایش دهیم، کنفرانس مهمی در مورد رمزنگاری در فرانسه برگزار می شود - و در آنجا در زمان ریشلیو رمزگذاری می کردند و رمزهای دیگران را در زمان ویتا شکستند."
واسیا به سرعت متوجه شد که قبلاً همه نقاشی های لوور را در جایی دیده است، دیدن برج ایفل حتی قبل از اینکه موش آن را از روی فرش پاک کند برایش خسته کننده شد و ما چنین هرم های شیشه ای را برای انواع کیوسک ها می سازیم و غذاخوری های مشکوک در یک کلام، در پاریس به سادگی چیزی برای دیدن وجود نداشت، جایی برای ماهیگیری وجود نداشت، بنابراین واسیا مجبور بود در گزارش های کنفرانس شرکت کند.
یکی از سخنرانان که بار دیگر سعی در کشف رمزهای بیکن داشت، این فرضیه را مطرح کرد که کلید اسرار بیکن را می توان با تجزیه و تحلیل همه زیر رشته های ممکن آثار بیکن پیدا کرد. "اما تعداد آنها خیلی زیاد است!" واسیا با صدای بلند تعجب کرد. "نه، نه چندان!" - گوینده فریاد زد، - "حساب کن، خودت خواهی دید!"
همان شب، واسیا آثار کامل بیکن را در اینترنت پیدا کرد. او برنامه ای نوشت که متون را به یک خط طولانی تبدیل می کرد و تمام فاصله ها و علائم نگارشی را از متن ها حذف می کرد. و اکنون واسیا بسیار متحیر است - چگونه تعداد زیر رشته های مختلف این رشته را بشماریم؟ 

ورودی
ورودی حاوی یک رشته غیر خالی است که توسط Vasya دریافت شده است. رشته فقط از حروف کوچک لاتین تشکیل شده است. طول آن از 2000 کاراکتر تجاوز نمی کند. 

خروجی
تعداد زیر رشته های مختلف این رشته را چاپ کنید.

 

نمونه‌ها
<سر> <بدن>
# ورودی خروجی
1 aaba 8