برنامه ای که بزرگترین زیر رشته متقارن یک رشته رو چاپ میکنه

[hadi_joulaee]

برنامه ای که بزرگترین زیر رشته متقارن یک رشته رو چاپ میکنه.مثلا در رشته ای مانند hoohoohasddsa بزرگترین زیر رشته متقارن hoohooh میباشد.


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

:8: :5: :31:

[hamidreza_buddy]

فک کنم order ش خیلی بالا باشه. یک رشتۀ طولانی (مثلاً به اندازۀ 100) بش بده ببین سریع جواب میده.
احتمالاً باید برای همچین کاری از برنامه نویسی پویا(Dynamic Programming) استفاده کنی.

[hadi_joulaee]

آره این برنامه ای بود که استادمون گفته بود با پوینتر ها بنویسین ولی من بدون استفاده از اونا نوشتمش . حرف شما هم درسته! ولی واسه نمونه برنامه بدی نیست

[hamidreza_buddy]

آقا یه روش به ذهنم رسید.

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

برای اینکه این مسئله رو حل کنیم، می تونیم که رشتۀ اول (S) رو خود رشته و رشتۀ دوم (T) رو معکوس رشته بفرستیم.
نتیجه بزرگترین زیر رشته متقارن یک رشته رو بدست می یاره.

[setareh.a]

اگر بخوایم الگوریتم زیر رشته مشترک رو برای دو فایل متنی انجام بدیم که زیر رشته رو در قالب یه فایل دیگه بده،باید چه کار کنیم؟

[dr.b4ne]

اگر بخوایم الگوریتم زیر رشته مشترک رو برای دو فایل متنی انجام بدیم که زیر رشته رو در قالب یه فایل دیگه بده،باید چه کار کنیم؟

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