المپدیا

الفبای $A$ شامل $k$ کاراکتر و عدد $n$ داده شده است. می‌خواهیم تعداد کوتاه‌ترین رشته‌های دایره‌ای از $A$ را به‌دست آوریم که هر رشته $n$ حرفی ممکن از $A$ دقیقا یک بار به صورت یک زیررشته متوالی در آن دیده شود. به عنوان مثال اگر $k$ برابر ۲ و $n$ برابر ۳ داده شود دو رشته زیر خاصیت خواسته شده را دارند: 00010111 11101000 چرا که در آن‌ها زیررشته‌های زیر دقیقا یک بار مشاهده می‌شود: 000, 001, 010, 011, 100, 101, 110, 111

برای ساخت رشته مورد نظر به دو روش می‌توانیم عمل کنیم. در یک روش می‌توان گراف $k^n$ رأسی که هر رأس آن یک دنباله $n$ تایی ممکن از الفبای $A$ باشد را در نظر گرفته و یال $x$ به $y$ وجود داشته باشد اگر $n-1$ حرف آخر $x$ با $n-1$ حرف اول $y$ برابر باشد. در این صورت از دور همیلتونی موجود در این گراف رشته مورد نظر یافت می‌شود.

روش دیگر آن است که گراف $k^{n-1}$ رأسی با رئوس متشکل از رشته‌های $n-1$ حرفی از $A$ را در نظر بگیریم و شرط وجود یک یال مانند روش قبل باشد. در این صورت با پیمایش هر یال دقیقا یک رشته $n$ حرفی از $A$ در رشته موردنظر به وجود می‌آید. چرا که در انتقال از یک رأس $n-1$ حرفی به رأسی دیگر که از شرط اشتراک پیشوند و پسوند $n-2$ حرفی خود پیروی می‌کنند، یک رشته‌ی $n$ حرفی منحصر به فرد ایجاد می‌شود. همچنین هر رشته $n$ حرفی از تداخل دو رشته $n-1$ حرفی صورت می‌گیرد، بنابراین پیمایش هر یال دقیقا متناظر با ایجاد یکی از زیررشته‌های $n$ حرفی مطلوب در رشته موردنظر است. بنابراین با پیمایش تور اویلری این گراف، با توجه به این که هر یال را دقیقا یک‌بار می‌پیماید کوتاه‌ترین رشته مطلوب را ایجاد می‌نماید.

گراف ساخته شده در این مسأله $k^{n-1}$ رأس از درجه $k$ دارد، از طرفی یافتن تور اویلری در زمان $O(N+E)$ قابل پیاده سازیست. بنابراین حل این مسأله از طریق تور اویلری در زمان $O(k^n)$ قابل پیاده سازیست.

در حال تکمیل.

نمونه مسأله در کدفورسز

wikipedia