تابع پیشوند، تابع Z


برای حل این مشکل، شمارش معمول کار نخواهد کرد، زیرا مجانبی آن O(t*s) خواهد بود. بنابراین، برای کارهای جستجوی زیر رشته ای، از الگوریتم KMP (Knuth-Morris-Pratt) استفاده می شود.
برای پیاده سازی این الگوریتم، از تابع پیشوند رشته استفاده می شود، این آرایه ای از اعداد طول n (strong>s طول) است که در آن هر عنصر  حداکثر طول است. از بزرگترین پسوند خود رشته فرعی s، با پیشوند آن مطابقت دارد. به عنوان مثال:
  <بدن>
خط عملکرد پیشوند یادداشت
abababcab 0 0 1 2 3 4 0 1 2  
abcabcd 0 0 0 1 2 3 0  
aabaaab 0 1 0 1 2 2 3  

الگوریتم تابع پیشوند بی اهمیت با مجانبی O(n^3):

ایجاد شد 
بردار<int> prefix_function (رشته ها) {
int n = (int ) s.length();
بردار<int>pi(n);
برای (int i=0; i<n; ++i)
برای (int k=0; k<=i; ++k)
اگر (s.substr(0,k) == s .substr(i-k+1،k))
pi[i] = k;
بازگشتpi;
}

و اکنون باید یک تابع پیشوند برای رشته ای از فرم بسازیم: & nbsp; t + # + s، که در آن # یک کاراکتر جداکننده است که به وضوح در متن نیست.  با تجزیه و تحلیل مقادیر تابع پیشوند پس از کاراکتر جداکننده مربوطه، باید توجه داشت که اگر مقدار حاصل برابر با طول زیر رشته مورد نظر باشد، وقوع آن پیدا می شود. به عنوان مثال، برای رشته "abababcab» و زیر رشته مورد نظر "abab"، تابع پیشوند به صورت:
خواهد بود 0 0 1 2 0 1 2 3 4 3 4 0 1 2 ما باید عناصر رشته مربوطه s را تجزیه کنیم:
1 2 3 4 3 4 0 1 2 - دو مورد وجود دارد که مقدار آن 4 است (4 و 6)، یعنی. طول t،  در نتیجه، پاسخ باید نوشته شود: 4 - 4 (طول t) & nbsp; = 0 و 6 - 4 = 2. مشاهده می شود که اینها پاسخ های صحیح و رشته "abab" در واقع یک زیر رشته در رشته "abababcab" در موقعیت های 0 و 2.

 

Training problem

(C++) جستجوی زیر رشته، KMP، نوع بی اهمیت: شروع

پس از بهینه سازی تابع پیشوند (برای جزئیات اینجا)، الگوریتم نهایی را با مجانبی O(n) بدست می آوریم:

ایجاد شد 
بردار<int> prefix_function (رشته ها) {
int n = (int ) s.length();
بردار<int>pi(n);
برای (int i=1; i<n; ++i) {
int j = pi[i-1< /span>]؛
در حالی که (j > 0 && s[i] != s[j])
j = پی[j-1];
اگر (s[i] == s[j]) ++j;
pi[i] = j;
}
بازگشتpi;
}

Training problem

تابع پیشوند

تابع
Z-
Z-function از رشته S - آرایه Z که هر عنصر آن Z است [i ] برابر است با طولانی ترین پیشوند رشته فرعی که از موقعیت i در رشته S شروع می شود، که همچنین پیشوند کل رشته Z. مقدار تابع Z- در موقعیت صفر معمولاً یا صفر یا طول کل رشته است.
مشکل
O(|S| ^ 2) یا O(|S|).
 
تابع پیشوند از رشته S - آرایه P که هر عنصر آن P[i] برابر است با طولانی‌ترین پسوند رشته فرعی که از موقعیت i در رشته S شروع می شود، که همچنین پسوند کل رشته S است. مقدار P-function در موقعیت صفر معمولاً صفر یا طول کل رشته است. 
مشکل
O(|S| ^ 2) یا O(|S|).
 
سعی کنید تابع Z و تابع پیشوند برای ​​O(|S| ^ 2) را اجرا کنید .

Training problem

تابع Z

 
هم Z و هم پیشوند تابع را می توان برای پیاده سازی الگوریتم KMP(Knuth-Morris-Pratt) برای یافتن یک رشته فرعی در یک رشته در O(|S|) استفاده کرد. ماهیت این الگوریتم به شرح زیر است: ما به رشته ای که می خواهیم رشته ای را که در آن جستجو می کنیم نسبت می دهیم. بسیار مطلوب است که یک کاراکتر جداکننده بین این خطوط قرار دهید، یعنی کاراکتری که در هیچ خطی (معمولا #) وجود ندارد.

Training problem

رمز