sobhan.s68
چهارشنبه 04 فروردین 1395, 14:35 عصر
سلام
به دنبال الگوریتی برای یافتن تعداد دنباله اعداد تکرار شونده در یک رشته عدد هستم . ورودی من یک رشته عدد بسیار طولانیه که برای که از چند تا زیر رشته یا دنباله عدد تکرار شونده بوجود آمده است .
از طریق چه الگوریتم هایی میتونم این مساله رو حل کنم ؟
فرض 1) تعداد نامشخصی زیر رشته (a1,a2,a3,a4,…) که از دنباله ای از اعداد صدرقمی که اعشاری هم میتوانند باشند (به صورت رندم و اتفاقی) تشکیل شده است موجود می باشد که از اعداد تشکیل دهنده این رشته ها و همچنین تعداد رشته ها اطلاعی نداریم . چیزی که در هر یک از این دنباله ی رشته ها مهم می باشد ترتیب اعداد دنباله می باشد نه رابطه بین آنها .
· فرض 2 ) یک رشته ی طولانی از میلیون ها عدد داریم که این رشته بزرگ از تکرار رشته های فرض 1، تولید شده است. نام این رشته را S می گذاریم.
حالت 1 : رشته های (a1,a2,a3,a4,…) برای تولید رشته s ، بدون تداخل و بدون ادغام شدن در یکدیگر هستند .
به عنوان مثال اگر دو رشته عدد (دنباله عدد)صد رقمی داشته باشیم ، رشته S از تکرار این دو رشته (دنباله عدد)بوجود آمده است. در این حالت هر یک از دنباله ی اعداد با یکدیگر تداخلی ندارند یعنی دنباله ی عدد یا تکرار شده یا بعد از دنباله ی دیگری می اید .
برای درک بهتر و ذکر مثال ، هر یک از رشته ها را 5 رقمی در نظر میگیریم .
A1=12345
A2=67891
...S=12345123451234567891678911234567891
اگز سه زیر رشته عدد (دنباله عدد) صد رقمی داشته باشیم رشته ی S از تکرار این سه رشته (دنباله عدد) بوجود آمده است .
و به همین ترتیب تعداد زیر رشته ها (a1,a2,a3,…) می توانند افزایش پیدا کنند و رشته ی S را تولید نمایند.
بیان مساله حالت 1 :
رشته s ، تولید شده و در اختیار ما قرار میگیرد . ما به دنبال الگوریتمی هستیم که با جستجو در رشتهS ،
اولا تعداد زیر رشته های (a1,a2,a3,a4,…) که در رشته S تکرار شده اند را تشخیص داده ،
دوما الگوی هر زیر رشته یا همان دنباله اعداد صد رقمی مربوط به هررشته ، که از تکرار آنها ، رشته S تولید شده است را مشخص نماید .
یعنی در واقع این الگوریتم ، باید تعداد رشته ها (a1,a2,a3,a4,…) و دنباله اعداد صد رقمی هر از این زیررشته ها که رشته S را تولید نموده را مشخص نماید . (ازرشته S به دنبال تشخیص زیر رشته ها هستیم )
برای راحتی کار، در این حالت رشته S در قالب دو سناریو ایجاد شده است که برای هر سناریو الگوریتم پیشنهادی باید تعداد رشته ها (a1,a2,a3,a4,…) و اعداد دنباله هر رشته را تشخیص دهد :
1-1 . رشته ی S از تکرار دو رشته (دنباله عدد) صد رقمی ( ( a1,a2 تولید شده است .
2-2 – رشته ی S از تکرار تعداد نامشخصی رشته (دنباله عدد) صد رقمی ( ( a1,a2,a3, … تولید شده است .
البته بدیهی میباشد که سناریو ی 2 سناریو 1 را هم پوشش میدهد .
حالت 2 : زیر رشته های (a1,a2,a3,a4,…) برای تولید رشته s ، در هم ادغام شده اند و ممکن است که هر رشته پس از اتمام رشته ی قبلی نیاید .
به عنوان مثال اگر دو رشته عدد (دنباله عدد)صد رقمی داشته باشیم ، رشته S از تکرار این دو رشته (دنباله عدد)بوجود آمده است. در این حالت دنباله ی اعداد با یکدیگر ممکن است هم تداخل نداشته باشند(مانند حالت 1) و هم ممکن است در هم ادغام شده باشند و اعداد دنباله ها در لابه لای یکدیگر آمده باشند .البته رعایت توالی اعداد هر یک از دنباله ها الزامی است.
برای درک بهتر و ذکر مثال ، هر یک از رشته ها را 5 رقمی در نظر میگیریم .
A1=12345
A2=56781
S=125637458112345567815671823415123451234512345123 45567815678112345
بیان مساله حالت 2 :
در حالت 2 هم ، دو سناریو مانند حالت 1 در نظر گرفته و به دنبال الگوریتمی هستیم که با توجه به رشته S تولید شده در حالت 2 ، پاسخگوی دو سناریو باشد .
به دنبال الگوریتی برای یافتن تعداد دنباله اعداد تکرار شونده در یک رشته عدد هستم . ورودی من یک رشته عدد بسیار طولانیه که برای که از چند تا زیر رشته یا دنباله عدد تکرار شونده بوجود آمده است .
از طریق چه الگوریتم هایی میتونم این مساله رو حل کنم ؟
فرض 1) تعداد نامشخصی زیر رشته (a1,a2,a3,a4,…) که از دنباله ای از اعداد صدرقمی که اعشاری هم میتوانند باشند (به صورت رندم و اتفاقی) تشکیل شده است موجود می باشد که از اعداد تشکیل دهنده این رشته ها و همچنین تعداد رشته ها اطلاعی نداریم . چیزی که در هر یک از این دنباله ی رشته ها مهم می باشد ترتیب اعداد دنباله می باشد نه رابطه بین آنها .
· فرض 2 ) یک رشته ی طولانی از میلیون ها عدد داریم که این رشته بزرگ از تکرار رشته های فرض 1، تولید شده است. نام این رشته را S می گذاریم.
حالت 1 : رشته های (a1,a2,a3,a4,…) برای تولید رشته s ، بدون تداخل و بدون ادغام شدن در یکدیگر هستند .
به عنوان مثال اگر دو رشته عدد (دنباله عدد)صد رقمی داشته باشیم ، رشته S از تکرار این دو رشته (دنباله عدد)بوجود آمده است. در این حالت هر یک از دنباله ی اعداد با یکدیگر تداخلی ندارند یعنی دنباله ی عدد یا تکرار شده یا بعد از دنباله ی دیگری می اید .
برای درک بهتر و ذکر مثال ، هر یک از رشته ها را 5 رقمی در نظر میگیریم .
A1=12345
A2=67891
...S=12345123451234567891678911234567891
اگز سه زیر رشته عدد (دنباله عدد) صد رقمی داشته باشیم رشته ی S از تکرار این سه رشته (دنباله عدد) بوجود آمده است .
و به همین ترتیب تعداد زیر رشته ها (a1,a2,a3,…) می توانند افزایش پیدا کنند و رشته ی S را تولید نمایند.
بیان مساله حالت 1 :
رشته s ، تولید شده و در اختیار ما قرار میگیرد . ما به دنبال الگوریتمی هستیم که با جستجو در رشتهS ،
اولا تعداد زیر رشته های (a1,a2,a3,a4,…) که در رشته S تکرار شده اند را تشخیص داده ،
دوما الگوی هر زیر رشته یا همان دنباله اعداد صد رقمی مربوط به هررشته ، که از تکرار آنها ، رشته S تولید شده است را مشخص نماید .
یعنی در واقع این الگوریتم ، باید تعداد رشته ها (a1,a2,a3,a4,…) و دنباله اعداد صد رقمی هر از این زیررشته ها که رشته S را تولید نموده را مشخص نماید . (ازرشته S به دنبال تشخیص زیر رشته ها هستیم )
برای راحتی کار، در این حالت رشته S در قالب دو سناریو ایجاد شده است که برای هر سناریو الگوریتم پیشنهادی باید تعداد رشته ها (a1,a2,a3,a4,…) و اعداد دنباله هر رشته را تشخیص دهد :
1-1 . رشته ی S از تکرار دو رشته (دنباله عدد) صد رقمی ( ( a1,a2 تولید شده است .
2-2 – رشته ی S از تکرار تعداد نامشخصی رشته (دنباله عدد) صد رقمی ( ( a1,a2,a3, … تولید شده است .
البته بدیهی میباشد که سناریو ی 2 سناریو 1 را هم پوشش میدهد .
حالت 2 : زیر رشته های (a1,a2,a3,a4,…) برای تولید رشته s ، در هم ادغام شده اند و ممکن است که هر رشته پس از اتمام رشته ی قبلی نیاید .
به عنوان مثال اگر دو رشته عدد (دنباله عدد)صد رقمی داشته باشیم ، رشته S از تکرار این دو رشته (دنباله عدد)بوجود آمده است. در این حالت دنباله ی اعداد با یکدیگر ممکن است هم تداخل نداشته باشند(مانند حالت 1) و هم ممکن است در هم ادغام شده باشند و اعداد دنباله ها در لابه لای یکدیگر آمده باشند .البته رعایت توالی اعداد هر یک از دنباله ها الزامی است.
برای درک بهتر و ذکر مثال ، هر یک از رشته ها را 5 رقمی در نظر میگیریم .
A1=12345
A2=56781
S=125637458112345567815671823415123451234512345123 45567815678112345
بیان مساله حالت 2 :
در حالت 2 هم ، دو سناریو مانند حالت 1 در نظر گرفته و به دنبال الگوریتمی هستیم که با توجه به رشته S تولید شده در حالت 2 ، پاسخگوی دو سناریو باشد .