هر Deterministic Final-State Automation (بطورخلاصه DFA) یک گراف جهتدار است که هر راس آن یک state نامیده میشود و روی هر یال آن یک حرف الفبا نوشته شده است. همچنین به ازای هر راس $s$ حرف روی یالهایی که از آن خارج میشود متفاوت است. دقت کنید که امکان دارد تعدادی یال با حرف یکسان بهیک راس وارد شوند.
هر DFA یک state شروع و تعدادی state پایان دارد. یک DFA یک رشته را میپذیرد اگر و فقط اگر یک گشت از state شروع آن بهیکی از stateهای پایان آن وجود داشته باشد که اگر حروف نوشته شده روی یالهای آن را به ترتیب کنار هم بچینیم برابر با رشته مورد نظر شود.
زبان یک DFA مجموعهای از رشتههایی است که آن DFA میپذیرد. به شما تعدادی رشته داده شده است، برنامهای بنویسید که کمترین $k$ای را بیابد کهیک DFA با $k$ state وجود داشته باشد که زبان آن برابر با مجموعه رشتههای ورودی باشد.
در تنها سطر خروجی جواب مسئله را چاپ نمایید.
| ورودی نمونه | خروجی نمونه |
|---|---|
| 3 fix foo ox | 5 |
| 4 a ab ac ad | 3 |