سلام.
در مساله رشته یا کلمه w شامل n حرف داده شده.
- p is a suffix of r, or r is a suffix of p, or r is equal to p;
- s is a prefix of r, or r is a prefix of s, or r is equal to s;
- r has minimal possible lengt
برای حلش از هر دو سطر اول و دوم یکی از شرایط باید رعایت شه. و تعداد بینهایت رشته برای هر کدوم تولید میشه. که اشتراک عبارات تولید شده برای اولی و دومی تعداد کمی کلمه می شه. حالا بنا به سطر آخر کوچکترین کلمه می شه ریشه محلی در نقطه i.
اگه i حرف اول رو تو p بذاریم و بقیه رو تو s:
عبارات تولید شده برای سطر اول:
- p پسوند r هست: در این صورت r شامل تمام رشته های زیر هست: (به جای ... هر چیزی می تونید بذازید)
...p
2. r پسوند p هست:
p=...r
3. r=p
برای سطر دوم:
1. s پیشوند r هست:
r=s...
2. r پیشوند s باشه:
s=r...
3. r=s
حالا اشتراک سطر اول و دوم می شه تعدادی کلمه که کوچکترین اونها می شه r تو نقطه i. مساله می خاد ما r رو برای تمام i ها بدست بیاریم و بزرگترینشو انتخاب کنیم.
برای اینکه واضح تر بشه یه مثال می زنم:
w=aababaaa
i=5
p=aabab , s=aaa
r=...aabab (1) or aabab=...r (2) or r=aabab (3)
and
r=aaa... (10) or aaa=r... (20) or r=aaa (30)
عباراتی که از 2 برای r نتیجه میشه: r=b,r=ab,r=bab,r=abab
عباراتی که از 20 نتیجه میشه: r=a,r=aa
کوتاه ترین عبارتی که تو 1 و 10 صدق کنه r=aaabab هست.
با توجه به "یا"ها و "و"ها کوتاهترین عبارتیکه میشه تولید کرد r=aaabab هست.
امیدوارم توضیحاتم کامل و واضح بوده باشه.
پاسخ با نقل قول