03 شهریور 1391, 10:19 ب.ظ
04 شهریور 1391, 12:43 ق.ظ
من خلاصه توضیح میدم اگه متوجه نشدین بگید تا کامل تر توضیح بدم.
ببینید ما وقتی داریم [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] است.
فکر کنم دیگه خلاصه هم نگفتم.
امیدوارم مفید بوده باشه.
ببینید ما وقتی داریم [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] است.
فکر کنم دیگه خلاصه هم نگفتم.
امیدوارم مفید بوده باشه.