یک $compact-trie$ نوعی $trie$ است که روی هر یال آن به جای یک حرف، یک رشته نوشته شده است.

فرض کنید یک رشته‌ی $s$‌داریم یک $prefix-trie$ از روی این رشته به این صورت ساخته می‌شود. به ازای هر $i$ کم‌تر مساوی طول رشته‌ی $s$، رشته‌ای از حروف $i$ام، $i+1$ام،… تا آخر رشته‌ی $s$ تشکیل شده است را در $trie$ وارد می‌کنیم. یک $compact-prefix-trie$ برای رشته‌ي $s$‌یک $prefix-trie$ است که $compact$ نیز می‌باشد.

فرض کنید یک جعبه‌ی سیاه داریم که برای یک رشته‌ی $s$ در زمان $O(n)$، $compact-prefix-trie$ آن را محاسبه می‌کند( می‌توانید فرض کنید که این درخت حداکثر $O(n)$ راس دارد. در ضمن جعبه‌ی سیاه کلیه‌ي یال‌ها و رئوس $trie$ را به ما می‌دهد.)

می‌گوییم رشته‌ی $w$ زیر رشته‌ی رشته‌ی $v$ است، (فرض کنید طول رشته‌ی $w$،$l_w$ باشد) اگر یک $i$ وجود داشته باشد به طوری که رشته‌ای که از حروف $i$ام، $i+1$ام،… تا $i+l_w-1$ام رشته‌ی $v$ تشکیل شده است مشاوی رشته‌ی $w$ باشد.

مسئله‌ی $LCS$($longest-common-substring$) به این صورت تعریف می‌شود:

دو رشته‌ی $s$ و $v$ داده شده است. بزرگ‌ترین رشته‌ای را بیابید که هم زیر رشته‌ی $s$ و هم زیر رشته‌ی $v$ باشد.

الگوریتمی از $O(n)$ بیابید که مسئله‌ی $LCS$ را حل کند.(بالتبع می‌توانید در راه حل خود از جعبه‌ی سیاه استفاده کنید.)

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