برای حل این مشکل، شمارش معمول کار نخواهد کرد، زیرا مجانبی آن 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.