# پرسش ۱۰ تمرین ۵
محسن زارع - ۴۰۳۱۰۶۰۱۳

## هینت

محل تغییر جهت در رشته‌ی T را در نظر بگیرید. اگر بتوان برابری زیررشته‌ها را پس از یک پیش‌پردازش در زمان O(1) بررسی کرد به سادگی میتوان مسئله را حل کرد .
## ایده‌ی حل

برای حل این مسئله باید بررسی کنیم که آیا می توان رشته ی T را با یک حرکت به سمت راست و سپس یک حرکت به سمت چپ روی رشتهی S ساخت یا خیر.

-۱برای اینکه مجبور نباشیم زیررشته مقایسه کنیم، ابتدا روی رشته
به کاراکتر ها را بارها و بارها به صورتکاراکتری S و
روی معکوس آن
همچنین Hash محاسبه می کنیم. به این ترتیب، بعد از یک پیشپردازش اولیه، مقایسهی هر زیررشته تنها
در زمان O(1) انجام می شود.

نکته ی تکمیلی:
پیشپردازش هش

ایده این است که برای رشته ی S یک هش پیشوندی بسازیم.

برای هر موقعیت i تعریف می کنیم:

H[i] = H[i − 1] × B + S[i]

که در آن:

• B یک عدد پایه (مثلاً 31 یا 911382323) است.
• H[i] هش پیشوند رشته تا اندیس i را نگه می دارد.

همچنین توان های B را هم از قبل ذخیره میکنیم:

P[i] = B^i

حالا هش هر زیررشته ی S[l..r]

در زمان ثابت به دست می آید:

Hash(l,r) = H[r] − H[l − 1] × P[r − l + 1]

بنابراین بعد از پیش پردازش، دیگر لازم نیست کاراکترها را یک به یک مقایسه کنیم.

-۲سپس هر موقعیت از رشتهی T را به عنوان محل تغییر جهت در نظر می گیریم؛ یعنی فرض می کنیم تا آن نقطه به سمت راست حرکت کرده ایم و از آنجا به بعد به سمت چپ برگشته ایم (pivot در نظر می گیریم).

-۳حالا تمام نقاط شروع ممکن در رشتهی S را بررسی می کنیم. برای هر نقطه شروع و هر محل تغییر جهت، دو قسمت رشته T را با بخش های متناظر در S مقایسه می کنیم:

• قسمت اول با حرکت به راست،
• و قسمت دوم با حرکت به چپ.

از آنجا که این مقایسه ها با استفاده از Hash انجام می شوند، هر بررسی در زمان ثابت انجام می شود. اگر هر دو قسمت با هم تطابق داشته باشند، یعنی T قابل تولید است.

## پیچیدگی

پیشپردازش Hash برابر O(|S|) است. سپس برای هر نقطه شروع در S و هر محل تغییر جهت در T یک بررسی زمان ثابت انجام می دهیم؛ بنابراین پیچیدگی الگوریتم برابر است با:

O(|S| × |T|)

که در بدترین حالت O(n^2) خواهد بود.