با نزدیک شدن مسابقه برنامه نویسی $ACM$ تهران، تیم $MIT$ خود را بیش‌تر و بیش‌تر آماده می‌کند تا در نهایت بتواند برای مرحله نهایی پذیرفته شود. هرسه نفر عضو تیم اکنون یکی از خبره‌ترین افراد در طراحی و پیاده سازی الگوریتم های ساده و پیچیده هستند، اما همگی از سرعت تایپ پایین رنج می‌برند. اگر آن‌ها سال‌های زیادی است که با شروع به تایپ کرده اند، اما سرعت آن‌ها با یک برنامه نویس مبتدی چندان تفاوت نمیکند. با توجه به وقت محدودی که در مسابقه برای هر سوال وجود دارد، این مشکل می‌تواند سبب گرفتن نتیجه ای نامطلوب برای تیم شود.

برای تحقق رویای شرکت در مرحله نهایی مسابقه، اعضای تیم تصمیم به ایجاد نرم افزار $ACT$ ($AutoComplete Tool$) برای تسریع در تایپ کردن کلمات کرده‌اند. این نرم افزار با هدف کاهش تعداد فشار دادن دکمه‌ها برای تایپ کد یا متن با پیش بینی کلمات ایجاد می‌شود. فرض میکنیم این نرم افزار تمام کلمات متنی که باید تایپ شود را میداند. $ACT$ برای هر متن یک جدول تناظر می‌سازد که یک رشته از حروف مانند $s$ را به یکی از کلمات متن مانند $w(s)$ متناظر میکند طوری که $s$ یک پیش-رشته ($prefix$) غیر تهی از $w(s)$ است و از این جدول برای پیشنهاد کلمه $w(s)$ به کاربر استفاده می‌کند، هنگامی که کاربر رشته $s$ را تایپ کرده است. همچنین پیشنهاد‌های $ACT$ هماهنگ نیز هستند، به این معنی که اگر برای رشته $s$ کلمه $w(s)$ پیشنهاد شود و رشته $ss’$ نیز زیر رشته $w(s)$ باشد، برای این رشته نیز همان کلمه پیشنهاد خواهد شد. $ACT$ در حین تایپ کاربر و با تایپ هر حرف، اگر رشته $s$ تا به اینجا توسط کاربر تایپ شده باشد، کلمه $w(s)$ را (در صورت وجود) پیشنهاد می‌کند و اگر کاربر در این لحظه دکمه $enter$ را فشار دهد، کلمه پیشنهادی جایگزین کلمه تایپ شده می‌شود، و در صورتی که دکمه $\space$ را فشار دهد کلمه تایپ شده توسط خود کاربر تغییری نمی‌کند. اما در هر دو صورت یک جای خالی ($space$) پس از کلمه تایپ شده اضافه می‌شود. به طور مثال اگر فرض کنیم با متن $hello heat heats$ روبرو هستیم و $ACT$ در جدول خود رشته‌های $h$ و $hel$ را به ترتیب به کلمات $heats$ و $hello$ متناظر کند، کاربر می‌تواند به ترتیب با تایپ کردن حروف $h, e, l, enter, h, e, a, t, \space, h, enter$ می‌تواند متن مورد نظر را تایپ کند. با فرض اینکه $ACT$ جدول تناظر را به صورتی می‌سازد که تعداد فشار دادن کلید‌های مورد نیاز کمینه شود، کار شما یافتن این تعداد کمینه تعداد فشار دادن کلیدها با گرفتن متن ورودی است.

• محدودیت زمان: ۱۰ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

• سوال بعد
• سوال قبل