سلام
بچه ها کسی این الگوریتم تطابق الگوی رشته را فهمیده برای منم یه توضیحی بده
الگوریتمش تو صفحه ۷۹ ساختمان داده پوران هست
ممنون میشم
من خلاصه توضیح میدم اگه متوجه نشدین بگید تا کامل تر توضیح بدم.
ببینید ما وقتی داریم [tex]S_{i}[/tex] رو با [tex]P_{j}[/tex] مقایسه میکنیم، اگر این [tex]P_{j-k}[/tex] با [tex]P_{0}[/tex]و [tex]P_{j-k 1}[/tex] با [tex]P_{1}[/tex] و ... برابر بود یه شمارنده در [tex]F[/tex] ایجاد میشه که تعداد برابریها از اول رشته با [tex]P_{j-k}[/tex] تا اول رشته بعلاوه [tex]k[/tex] با [tex]P_{j}[/tex] هست . حالا در مقایسه اگر به تناقض رسیدیم و اگر شمارنده ای که مربوط به [tex]j[/tex] است غیر از [tex]-1[/tex] باشه یعنی این چندتا مقایسه آخر همون مقایسه هاییه که در اول باید انجام میدادیم خوب دیگه از عددی که شمارنده این [tex]j[/tex] نشون میده استفاده میکنیم و به تعداد این شمارنده داخل [tex]P[/tex] جلو میریم و عنصر بعدی [tex]S[/tex] رو باش مقایسه میکنیم.
مثال:
P=abaabb
S=aabaabaabb
خوب ما اول [tex]F[/tex] رو تشکیل میدیم.
P=a | b | a | a | b | b
F=-۱|-۱ | ۰ | ۰ | ۱ |-۱
j=۰ | ۱ | ۲ | ۳ | ۴ | ۵
خوب اول [tex]P_{0}[/tex] با [tex]S_{0}[/tex] مقایسه میشه موفقیت آمیزه حالا[tex]P_{1}[/tex] با [tex]S_{1}[/tex] مقایسه میشه ، برابر نیستن ، حالا به [tex]F_{0}[/tex] نگاه میکنیم [tex]-1[/tex] هست پس باید [tex]S_{1}[/tex] رو با [tex]P_{0}[/tex] مقایسه کنیم، که برابرن خوب حالا [tex]S_{2}[/tex] با [tex]P_{1}[/tex] مقایسه میشه و برابرن حالا [tex]S_{3}[/tex] با [tex]P_{2}[/tex] خوب اینم برابره
[tex]S_{4}[/tex] با [tex]P_{3}[/tex] اینم برابره.
[tex]S_{5}[/tex] با [tex]P_{4}[/tex] اینم برابره.
[tex]S_{6}[/tex] با P5 این برابر نیست.حالا به [tex]F_{(j-1)}[/tex] نگاه میکنیم یعنی [tex]F_{4}[/tex] خوب برابر [tex]1[/tex] هست . حالا بجای اینکه از اول شروع کنیم [tex]S_{i}[/tex] رو با [tex]P_{F_{(j-1)} 1}[/tex] مقایسه میکنیم که میشه مقایسه [tex]S_{6}[/tex] با [tex]P_{2}[/tex] که برابرند.
در ادامه [tex]S_{7}[/tex] با [tex]P_{3}[/tex] مقایسه میشه برابرند
[tex]S_{8}[/tex] با [tex]P_{4}[/tex] برابرند.
[tex]S_{9}[/tex] با [tex]P_{5}[/tex] برابرند .
و در نتیجه رشته [tex]P[/tex] زیر مجموعه رشته [tex]S[/tex] است.
فکر کنم دیگه خلاصه هم نگفتم.
امیدوارم مفید بوده باشه.