ورود

نسخه کامل مشاهده نسخه کامل : برنامه ای که بزرگترین زیر رشته متقارن یک رشته رو چاپ میکنه


hadi_joulaee
15-04-2007, 10:23
برنامه ای که بزرگترین زیر رشته متقارن یک رشته رو چاپ میکنه.مثلا در رشته ای مانند hoohoohasddsa بزرگترین زیر رشته متقارن hoohooh میباشد.


برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

:8: :5: :31:
hamidreza_buddy
15-04-2007, 20:40
فک کنم order ش خیلی بالا باشه. یک رشتۀ طولانی (مثلاً به اندازۀ 100) بش بده ببین سریع جواب میده.
احتمالاً باید برای همچین کاری از برنامه نویسی پویا(Dynamic Programming) استفاده کنی.
hadi_joulaee
17-04-2007, 10:14
آره این برنامه ای بود که استادمون گفته بود با پوینتر ها بنویسین ولی من بدون استفاده از اونا نوشتمش . حرف شما هم درسته! ولی واسه نمونه برنامه بدی نیست
hamidreza_buddy
17-04-2007, 15:41
آقا یه روش به ذهنم رسید.

یه الگوریتمی هست به نام Longest Common Substring که به عنوان ورودی دو رشته (S و T) می گیرد و بزرگترین زیررشتۀ مشترک این دو رشته را پیدا می کند. این الگوریتم از Dynamic Programming بهره می بره. فرض کنیم این الگوریتمو نوشته باشیم. الگوریتمش از اینجا ([ برای مشاهده لینک ، لطفا با نام کاربری خود وارد شوید یا ثبت نام کنید ]) ببینید. order این الگوریتم (O(mn هست که m طول S و n طول T . اگر اندازۀ دو رشته یکی باشد می شود (O(n^2 . که بهتر از الگوریتم بالایی هست که (O(n^3 .

برای اینکه این مسئله رو حل کنیم، می تونیم که رشتۀ اول (S) رو خود رشته و رشتۀ دوم (T) رو معکوس رشته بفرستیم.
نتیجه بزرگترین زیر رشته متقارن یک رشته رو بدست می یاره.
setareh.a
12-01-2012, 00:25
اگر بخوایم الگوریتم زیر رشته مشترک رو برای دو فایل متنی انجام بدیم که زیر رشته رو در قالب یه فایل دیگه بده،باید چه کار کنیم؟
dr.b4ne
16-02-2012, 01:21
اگر بخوایم الگوریتم زیر رشته مشترک رو برای دو فایل متنی انجام بدیم که زیر رشته رو در قالب یه فایل دیگه بده،باید چه کار کنیم؟

یعنی شما میتونی زیر رشته مشترک رو پیدا کنی و فقط نمیتونی بریزیش تو فایل ؟؟؟؟؟؟؟:hmm::hmm: