زمان کنونی: ۱۰ فروردین ۱۴۰۳, ۰۶:۲۴ ق.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

تطابق الگوی رشته

ارسال:
  

shahrzad sara پرسیده:

تطابق الگوی رشته

سلام
بچه ها کسی این الگوریتم تطابق الگوی رشته را فهمیده برای منم یه توضیحی بده
الگوریتمش تو صفحه ۷۹ ساختمان داده پوران هست
ممنون میشم

۱
ارسال:
  

javadem پاسخ داده:

تطابق الگوی رشته

من خلاصه توضیح میدم اگه متوجه نشدین بگید تا کامل تر توضیح بدم.
ببینید ما وقتی داریم [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] است.
فکر کنم دیگه خلاصه هم نگفتم.
امیدوارم مفید بوده باشه.



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  آیا کسایی که رشته شرایط خاص قبول شدن شانس قبولی برا رشته های انتخابی قبل اونو ندارن؟؟ mahyar12 ۱۹ ۱۲,۱۲۲ ۱۷ تیر ۱۳۹۷ ۱۰:۴۹ ق.ظ
آخرین ارسال: Mokhtar021
  نحوه انصراف از انتخاب رشته یا کد رشته Sepideh96 ۳ ۶,۱۴۲ ۱۰ آبان ۱۳۹۶ ۰۱:۱۱ ب.ظ
آخرین ارسال: pioneer01
  لیست انتخاب رشته پیشنهادی رشته آیتی هر دو گرایش alilash ۰ ۲,۰۱۷ ۲۲ خرداد ۱۳۹۶ ۱۲:۱۹ ب.ظ
آخرین ارسال: alilash
  اگه رشته کامپیوتر و آی تی وجود نداشت، میرفتم رشته ی ....؟! پروفسور ۷۱ ۱,۹۲۱ ۲۱ آذر ۱۳۹۵ ۰۹:۴۲ ق.ظ
آخرین ارسال: plusdeck
  سوال در مورد دفترچه ارشد، کد رشته "شبکه" و کد رشته "امنیت شبکه" sMohammad ۲ ۲,۴۰۴ ۱۸ آذر ۱۳۹۵ ۰۲:۰۷ ق.ظ
آخرین ارسال: sMohammad
  راهنمایی رشته های ارشد برای انتخاب رشته ۹۵ elahehma ۴ ۳,۳۲۶ ۲۹ خرداد ۱۳۹۵ ۰۱:۰۹ ب.ظ
آخرین ارسال: elahehma
  کمک در مورد انتخاب رشته ارشد (گیر کردن بین دو رشته متفاوت) nima20-20 ۱۱ ۵,۰۸۰ ۰۳ شهریور ۱۳۹۴ ۰۵:۲۱ ب.ظ
آخرین ارسال: khayyam
Star سوال در مورد تخصیص آی پی در شبکه ای با الگوی زیر شبکه خاص a.heidarnasab ۱ ۲,۲۱۳ ۱۰ خرداد ۱۳۹۴ ۰۹:۳۶ ب.ظ
آخرین ارسال: win2win
Shocked عدالت بین دانشجویان رشته کامپیوتر و آی تی با سایر رشته ها sabafarhadi ۳۰ ۱۱,۱۶۲ ۰۶ خرداد ۱۳۹۴ ۰۶:۵۸ ب.ظ
آخرین ارسال: پوونه
  تغیر رشته از رشته های انسانی به ای تی و انتخاب رشته دانشگاه ali139084 ۵ ۳,۰۰۲ ۲۶ اردیبهشت ۱۳۹۴ ۰۱:۳۴ ق.ظ
آخرین ارسال: Pure Liveliness

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close