===== مساله De Bruijn =====

الفبای $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)$ قابل پیاده سازیست.
===== پیاده سازی =====

در حال تکمیل.

===== مسائل نمونه =====

[[http://codeforces.com/contest/508/problem/D|نمونه مسأله در کدفورسز]]

 
===== مراجع =====
[[https://en.wikipedia.org/wiki/De_Bruijn_sequence|wikipedia]]